/ BOJ

BOJ_7576_토마토_JAVA

문제 : 토마토

링크 : BOJ_7576_토마토

접근 방식

BFS와 Depth를 이용하면 간단하게 풀 수 있는 문제였다. 나는 큐의 작동방식을 잊어버려 너무 복잡한 방식으로 접근하다가 시간을 엄청 허비했다.

큐는 선입선출 방식이다. 따라서 2차원 배열에 존재하는 토마토를 순서대로 큐에 집어넣은 뒤 BFS를 실행하면, 자동으로 먼저 들어간 토마토가 탐색을 하고 다음 탐색 노드가 큐의 마지막으로 들어간다. 미리 큐에 집어넣어두면 자동적으로 모든 토마토로부터의 탐색이 이루어지는 것이다. 나는 이 부분을 놓쳐서 큐를 각각 리스트로 만들어서 해결하려 했다.

아무튼, 문제풀이는 위와 같은 방법으로 하면 된다. 배열을 탐색하며 큐에 토마토의 위치와 깊이를 저장하고, bfs를 통해 모든 탐색이 완료 되었을 때 Depth 최댓값을 구한다. 그 후 배열을 다시 탐색하여 익지 않은 토마토(0)이 있다면 -1을 출력하고, 그렇지 않다면 저장한 Depth를 출력한다.

풀이 방법

  1. Node클래스를 생성한다. Node 클래스는 멤버변수로 x,y좌표와 depth 깊이를 저장한다.

  2. 배열의 크기 M과 N을 입력받아 저장하고, N*M 크기의 2차원 배열을 하나 생성한다. 같은 크기의 방문상태를 확인하는 배열, 그리고 토마토를 담을 queue도 생성한다.

  3. 배열의 크기만큼 반복한다. 배열에 값을 할당하면서, 그 값이 1(토마토)이라면 해당 토마토의 위치 Node를 생성해 큐에 offer한다.

  4. BFS 메서드를 수행한다. BFS 메서드는 큐를 이용해 구현한다.

  5. 큐가 전부 빌 때까지 반복한다. 먼저 Node를 생성하여 큐에서 poll 하여 저장한다.

  6. 해당 노드의 위치를 방문처리하고, 4방탐색을 진행한다. 만약 탐색이 가능한 상태라면 그 위치를 방문처리, 배열의 값을 1로 바꾸고, 탐색할 위치에 depth를 1 증가시켜 새로운 Node를 생성해 큐에 offer한다.

  7. 1번 반복이 진행될 때마다 depth의 max값을 answer 변수에 저장한다.

  8. 모든 반복이종료된 후 배열을 탐색한다. 배열에 0이 존재한다면 -1을 출력하고 프로그램을 종료한다.

  9. 그렇지 않다면 answer를 -1 해주고 출력한다.

소스 코드


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_7576_토마토2 {
	static int M, N, arr[][];
	static Queue<Node> queue;
	static int[][] dir = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
	static boolean[][] visited;
	static int answer;

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(in.readLine(), " ");

		M = Integer.parseInt(st.nextToken());

		N = Integer.parseInt(st.nextToken());

		arr = new int[N][M];
		queue = new LinkedList<>();
		visited = new boolean[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			for (int j = 0; j < M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());

				if (arr[i][j] == 1) {
					queue.offer(new Node(i, j, 1));
				}
			}
		}



		bfs();
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(arr[i][j] == 0) {
					System.out.println(-1);
					return;
				}
			}
		}
		System.out.println(answer-1);
	}

	static void bfs() {

		while (!queue.isEmpty()) {

			Node node = queue.poll();

			answer = Math.max(answer, node.depth);

			visited[node.x][node.y] = true;

			for (int d = 0; d < 4; d++) {
				int dx = node.x + dir[d][0];
				int dy = node.y + dir[d][1];

				if (dx >= 0 && dx < N && dy >= 0 && dy < M) {
					if (arr[dx][dy] == 0 && !visited[dx][dy]) {
						visited[dx][dy] = true;
						arr[dx][dy] = 1;
						queue.offer(new Node(dx, dy, node.depth + 1));
					}
				}
			}
		}
	}
}