백준 17086번: 아기 상어 2

문제 설명

• 각 좌표에서 8방이동이 가능합니다.
• 각각의 0을 기준으로 자신과 가장 가까운 1까지의 거리를 계산하고 그 거리들을 비교했을 때 가장 큰 값을 출력하는 문제입니다.

접근법

• 0을 기준으로 탐색할지, 아니면 1을 기준으로 탐색할지에 대한 고민이 필요합니다.
  • 1을 기준으로 하면 검사할 때마다 모든 board를 탐색해야 합니다.
  • 0을 기준으로 하면 검사하다가 1을 만나면 곧바로 종료할 수 있습니다.

저는 0을 기준으로 탐색을 진행했습니다.

• 종료조건
  • 0에서 탐색을 시작해 최초로 1을 만나게 되면 해당 탐색을 종료합니다.
• 깊이 계산
  • while문 안에 한번 더 while문을 사용해서 해당 노드의 차수를 기억하도록 구현했습니다.
  • visited에 1을 더하는 방법으로도 계산이 가능해 보입니다.

정답

package simple_test;

import java.util.*;
import java.io.*;

public class Test3 {
	static int M;
	static int N;
    //가독성 때문에 방향탐색 방법을 dx,dy로 바꾸기로 했습니다.
	final static int[][] d = { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, -1 }, { 0, 1 }, { 1, -1 }, { 1, 0 }, { 1, 1 } };

	public static void main(String[] args) throws IOException {
		int answer = Integer.MIN_VALUE;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		//board 만들기
		int[][] board = new int[M][N];
		for (int i = 0; i < M; i++) {
        	// 줄단위로 받으려면 여기서 받아야 합니다.
			StringTokenizer st2 = new StringTokenizer(br.readLine(), " "); 
			for (int j = 0; j < N; j++) {
				board[i][j] = Integer.parseInt(st2.nextToken());
			}
		}
        //완전탐색을 실행합니다.
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if (board[i][j] == 1)
					continue;
				answer = Math.max(BFS(i, j, board), answer);
			}
		}
		System.out.println(answer);
	}
	//queue의 크기마다 while문을 돌려서 depth를 저장하도록 구현했습니다.
	public static int BFS(int x, int y, int[][] board) {
		Queue<int[]> queue = new LinkedList();
		boolean[][] visited = new boolean[M][N];
		int[] start = { x, y };
		int depth = 0;
		queue.add(start);
		visited[x][y] = true;
		while (!queue.isEmpty()) {
			int size = queue.size(); // 이 시점에 queue에 같이 들어있는 값들은 모두 나의 형제들입니다.
			while (--size >= 0) { // 차수를 구분지어 계산하기 위해 while문을 한번 더 이용했습니다.
				int[] value = queue.poll();
				for (int i = 0; i < 8; i++) {
                	//종료조건, 최초로 1을 만나면 탐색을 멈춥니다
					if (0 <= value[0] + d[i][0] && value[0] + d[i][0] < M && 0 <= value[1] + d[i][1]
							&& value[1] + d[i][1] < N && board[value[0] + d[i][0]][value[1] + d[i][1]] == 1) {
						return ++depth;
					}
                    // 다음 값을 큐에 넣으면서 방문처리 해 줍니다.
					if (0 <= value[0] + d[i][0] && value[0] + d[i][0] < M && 0 <= value[1] + d[i][1]
							&& value[1] + d[i][1] < N && !visited[value[0] + d[i][0]][value[1] + d[i][1]]) {
						int[] a = { value[0] + d[i][0], value[1] + d[i][1] };
						queue.add(a);
						visited[value[0] + d[i][0]][value[1] + d[i][1]] = true;
					}
				}
			}
			++depth; // depth차수에 대한 탐색이 끝났기 때문에 depth를 늘립니다.
		}
		return depth;
	}

}

기타

• 메모리가 아주 아슬하게 통과하는 것 같습니다. 메모리를 효율적으로 활용할 수 있는 방법을 고민해 봐야 할 것 같습니다.