[백준] 16924 십자가 찾기 - Brute Force / Java

• 문제 링크

16924번: 십자가 찾기

 

• 풀이 과정

문제에 대한 접근 방식은 * 로 만들 수 있는 십자가를 찾는 것이 아닌,

갖가지 크기의 십자가만이 주어졌을 때 예제 입력의 상태로 만들 수 있는 지를 찾는 것이다.

 

따라서 십자가를 적용할 수 있는 시작점을 map 배열의 n - 1 * m - 1 의 범위내에서 찾고

해당 시작점에서 4 방향을 모두 탐색 가능할 시, 십자가를 적용할 수 있는 경우이므로

탐색한 모든 좌표를 boolean 배열에 방문 표시한다.

 

십자가의 개수를 나타내는 변수 cnt++ 을 수행하고

시작점의 좌표와 십자가의 크기(depth) 를 StringBuilder 객체 sb에 저장한다.

 

이 후 시작점 좌표와 depth + 1 을 매개변수로 전달해 재귀 호출하여 더 큰 크기의 십자가가 적용 가능한지 확인한다.

 

끝으로 map 배열의 좌표가 * 이고 아직 방문하지 않았다면 십자가만을 이용해서 입력의 상태를 만들 수 없는 것이므로

-1 을 출력하고 아니라면 cnt 변수와 십자가 좌표와 크기가 저장된 sb 를 정답으로써 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	static int n, m, cnt;
	static char[][] map;
	static boolean[][] visit;
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		map = new char[n][m];
		visit = new boolean[n][m];

		for (int i = 0; i < n; i++) {
			String input = br.readLine();
			for (int j = 0; j < m; j++)
				map[i][j] = input.charAt(j);
		}

		for (int i = 1; i < n - 1; i++) {
			for (int j = 1; j < m - 1; j++) {
				if (map[i][j] == '*')
					recur(i, j, 1);
			}
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] == '*' && !visit[i][j]) {
					cnt = 0;
					break;
				}
			}
		}

		bw.write(cnt == 0 ? "-1" : (cnt + "\n" + sb));
		bw.flush();
	}

	private static void recur(int y, int x, int depth) {
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i] * depth;
			int nx = x + dx[i] * depth;

			if (ny < 0 || nx < 0 || ny >= n || nx >= m)
				return;

			if (map[ny][nx] == '.')
				return;
		}

		visit[y][x] = true;
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i] * depth;
			int nx = x + dx[i] * depth;

			visit[ny][nx] = true;
		}

		cnt++;
		sb.append((y + 1) + " " + (x + 1) + " " + depth + "\n");

		recur(y, x, depth + 1);
	}

}