백준 알고리즘: 7576번 토마토

문제 정보

---

 

7576번: 토마토

 

핵심

---

역시 이전 문제와 비슷한 BFS(너비 우선 탐색)을 활용하여 풀이하는 문제이다

이 문제에서 하루가 지나면 익은 토마토의 상하좌우의 익지 않은 토마토들은 익은 토마토로 변하게 되는데,

모든 익지 않은 토마토가 익은 토마토가 될 때까지의 최소 날짜를 출력하는 것이다

하지만,

1. 익지 않은 토마토(0)가 모두 익은 토마토(1)로 변했음을 어떻게 파악할지

2. 익은 토마토로 변했을때 최소 날짜는 어떻게 카운팅하는 것이 좋을지

 

이 두가지의 경우에서 생각하기 조금 힘들었던 것 같다

나는 다음과 같이 풀이하였다

 

1. 익지 않은 토마토(0)가 모두 익은 토마토(1)로 변했음을 어떻게 파악할까?

    for (int i = 0; i < N; i++) {
      st = new StringTokenizer(br.readLine());
      for (int j = 0; j < M; j++) {
        int number = Integer.parseInt(st.nextToken());
        map[i][j] = number;
        if (number == 0) {
          numberOfZero++;
        } else if (number == 1) {
          queue.add(new Node(i, j, 0));
        }
      }
    }

numberOfZero 라는 int형 변수를 두고, map을 입력받을 때 0(익지 않은 토마토)가 들어올때마다 하나씩 카운팅해 준다

if (!visited[nextRow][nextCol] && map[nextRow][nextCol] == 0) {
  visited[nextRow][nextCol] = true;
  map[nextRow][nextCol] = 1;
  numberOfZero--;
  // do something

그리고, bfs를 수행할 때 방문하지 않았고 익지 않은 토마토가 있는 자리라면 익은 토마토(1) 로 바꿔주며 numberOfZero를 1씩 줄여간다

 

2. 익은 토마토로 변했을때 최소 날짜는 어떻게 카운팅하는 것이 좋을지

if (numberOfZero == 0) {
  return current.depth + 1;
}

numberOfZero가 0이 되면, 현재 depth에 1을 더한 값을 리턴해주면 답이 된다

여기서 왜 depth + 1이 답이 되는지는 아래 풀이에서 설명하겠다

 

 

풀이

---

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

class Main {

  static boolean[][] visited;
  static Queue<Node> queue;
  static int[][] plusNumber = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

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

    int M = Integer.parseInt(st.nextToken());
    int N = Integer.parseInt(st.nextToken());
    int[][] map = new int[N][M];
    visited = new boolean[N][M];
    queue = new LinkedList<>();
    int numberOfZero = 0;

    for (int i = 0; i < N; i++) {
      st = new StringTokenizer(br.readLine());
      for (int j = 0; j < M; j++) {
        int number = Integer.parseInt(st.nextToken());
        map[i][j] = number;
        if (number == 0) {
          numberOfZero++;
        } else if (number == 1) {
          queue.add(new Node(i, j, 0));
        }
      }
    }
    System.out.println(bfs(map, numberOfZero, N, M));


  }

  public static int bfs(int[][] map, int numberOfZero, int N, int M) {
    while (!queue.isEmpty()) {
      Node current = queue.poll();

      // 하루가 지나는 동안 각 토마토에게 전이되는 주변 토마토들
      for (int[] number : plusNumber) {
        int nextRow = current.row + number[0];
        int nextCol = current.col + number[1];
        if (nextRow < 0 || nextRow >= N || nextCol < 0 || nextCol >= M) {
          continue;
        }
        if (!visited[nextRow][nextCol] && map[nextRow][nextCol] == 0) {
          visited[nextRow][nextCol] = true;
          map[nextRow][nextCol] = 1;
          numberOfZero--;
          if (numberOfZero == 0) {
            return current.depth + 1;
          }
          queue.add(new Node(nextRow, nextCol, current.depth + 1));
        }
      }

    }
    return numberOfZero == 0 ? 0 : -1;
  }
}

class Node {

  int row;
  int col;
  int depth;

  public Node(int row, int col, int depth) {
    this.row = row;
    this.col = col;
    this.depth = depth;
  }
}

1. 입력받을 때, 익지 않은 토마토는 카운팅해주고 익은 토마토는 queue에 Node로 좌표를 wrapping하여 집어넣는다

이때, depth는 0에서 시작한다(초기 상태)

 

2. 큐에서 노드를 꺼내고, 상하좌우 위치에 있는 방문하지 않은 && 안익은 토마토를 익은 토마토로 바꾸고 방문 표시를 한다

0의 개수를 하나 줄여준다

 

3. 만약 방문 표시를 하던 중, numberOfZero가 0이 되면(모든 0이 1로 바뀌었다면) 현재 깊이에 +1을 하고 리턴한다

그 이유는,

- 현재 내가 방문했다고 표시하고 있는 노드는 내가 큐에 추가할 노드이다

- 현재 노드의 깊이는 current.depth이다

- 내가 큐에 추가한 노드의 깊이는 current.depth + 1 이다

- 마지막으로 큐에 추가한 노드의(0->1로 바뀐 마지막 노드) 깊이가 최단 걸린 시간이므로 depth+1을 해주는 작업이 반드시 필요하다

 

4. 만약 numberOfZero가 0인 상태로 큐가 비어있게 된다면?

- 이는 처음부터 queue에 아무 노드도 존재하지 않았음을 의미한다. 이미 완성된 상태이므로 0을 리턴한다

4-1. numberOfZero가 0이 아닌 상태로 큐가 비어있다면?

- 이는 더이상 안익은 토마토(0)를 익은 토마토(1)로 바꿀 경로가 존재하지 않는, 만들 수 없으므로 -1을 리턴한다

 

 

Source Code on GitHub

---