[백준] 16924 십자가 찾기 - 구현 + 시뮬레이션 + 브루트포스 JAVA

https://www.acmicpc.net/problem/16924

16924번: 십자가 찾기

코드설명

구현 브루트포스 시뮬레이션 문제입니다.

 

문제에서 유의해야할점은 4방향을 확인할떄 평소하던대로 dx, dy 이런식으로 4방향을 확인하지않고, 4방향으로 동시에 1개씩 이동하니 아래와 같이 확인하면 편하게 확인할 수 있습니다. 처음에 dx dy 를 사용하여 진행하다가 불필요하게 복잡해져서 코드가 길어졌었습니다.

for(int k=1; ;k++) {
    if( i - k < 0 || i + k >= N || j - k < 0 || j + k >= M) break;
    if(map[i - k][j] == '*' && map[i+k][j] == '*' && map[i][j - k] == '*' && map[i][j+k] == '*') {
        size = k;
    }else {
        break;
    }
}

문제 이해가 조금 헷갈리는데,예를드면 1번 예지입력같은경우 

6 8
....*...
...**...
..*****.
...**...
....*...
........


예제출력 1
2
3 4 1
3 5 2

위와 같이 출력되는것이지만, 문제에서는 
3
3 4 1
3 5 2
3 5 1

이와 같이 출력하여 헷갈렸었습니다. 
출력에 가능한 답이 여러가지인 경우에 아무거나 출력하는것이 조건이므로 중복되는 부분이 있을 수 있습니다.
또한 십자가의 개수는 NxM 이하이여야 하기에 사실상 모든 점에 십자가가 있어도 상관없습니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	public static int N,M;
	public static int answer = -1;
	public static char[][] map;
	public static boolean[][] answerVisited;
	public static ArrayList<Node> answerNode = new ArrayList<Node>();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	map = new char[N][M];
    	answerVisited = new boolean[N][M];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
			map[i] = st.nextToken().toCharArray(); 
    	}
    	
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<M;j++) {
    			if(map[i][j] == '*') {
    				int size = 0;
    				for(int k=1; ;k++) {
    					if( i - k < 0 || i + k >= N || j - k < 0 || j + k >= M) break;
    					if(map[i - k][j] == '*' && map[i+k][j] == '*' && map[i][j - k] == '*' && map[i][j+k] == '*') {
    						size = k;
    					}else {
    						break;
    					}
    				}
    				
    				if(size > 0) {
    					answerNode.add(new Node( i + 1, j + 1, size));
    					answerVisited[i][j] = true;
    					for(int k=1;k<=size;k++) {
    						answerVisited[i + k][j] = true;
    						answerVisited[i - k][j] = true;
    						answerVisited[i][j + k] = true;
    						answerVisited[i][j - k] = true;
    					}
    				}
    			}
    		}
    	}
    	
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<M;j++) {
    			if(map[i][j] == '*' && answerVisited[i][j] != true) {
    				System.out.println(answer);
    			}
    		}
    	}
    	
    	System.out.println(answerNode.size());
    	for(int i=0;i<answerNode.size();i++) {
    		System.out.println(answerNode.get(i).x + " " + answerNode.get(i).y + " " + answerNode.get(i).s);
    	}
    	
    }
	
	
	
}

class Node{
	int x;
	int y;
	int s;
	public Node(int x, int y , int s) {
		this.x=x;
		this.y=y;
		this.s=s;
	}
}