백준 2638번: 치즈 (Java)

접근

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

2638번: 치즈

간단한 bfs 문제였습니다.

맨 테두리에는 치즈가 없기 때문에 (0, 0) 부터 bfs 탐색을 하면서 visited 배열에는 다음과 같이 저장해줍니다.

1. 다음 위치가 0, 즉 치즈가 아닐 경우 큐에 다음 위치를 추가하고 visited[r][c] 에는 -1 을 저장합니다. visited 값이 -1 이라는 것은 이 위치를 더이상 탐색하지 않아도 된다는 뜻입니다.
2. 다음 위치가 1, 즉 치즈일 경우, 큐에 다음 위치를 추가하지는 않고, visited 배열 값을 1 더해줍니다. 이 때, visited 값이 2보다 크다면 해당 위치를 melt_list라는 별도의 LinkedList 에 저장해주고, visited 값을 -1로 바꿉니다. 이 위치는 더 많은 공기와 닿아있을 수 있지만 어차피 녹기 때문에 더이상 탐색하지 않아도 무관합니다.
3. 이렇게 탐색을 완전히 완료하고 나면, melt_list 에는 두면 이상이 공기중에 닿아있는 치즈 위치가 저장되어 있습니다.
4. 이 리스트가 비어있다면, 더이상 녹을 치즈가 없다는 뜻이므로 false 를 리턴합니다.
5. 이 리스트가 비어있지 않다면 해당 위치들에서 치즈를 없다고 표시해줍니다.

위의 탐색 과정을 몇번 반복할 수 있는지 계산함으로써 문제를 해결할 수 있습니다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;

public class Main {

  static int N, M, ans;
  static int[][] map;
  static int[] dr = { 0, 1, 0, -1 };
  static int[] dc = { 1, 0, -1, 0 };

  static class Node {

    private int r, c;

    public Node(int r, int c) {
      this.r = r;
      this.c = c;
    }
  }

  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 int[N][M];
    for (int i = 0; i < N; i++) {
      st = new StringTokenizer(br.readLine());
      for (int j = 0; j < M; j++) {
        map[i][j] = Integer.parseInt(st.nextToken());
      }
    }
    br.close();
    while (melt()) ans++;
    System.out.println(ans);
  }

  static boolean melt() {
    LinkedList<Node> queue = new LinkedList<>();
    LinkedList<Node> melt_list = new LinkedList<>();
    int[][] visited = new int[N][M];
    queue.add(new Node(0, 0));
    visited[0][0] = -1;
    while (!queue.isEmpty()) {
      Node now = queue.poll();
      for (int i = 0; i < 4; i++) {
        int nr = now.r + dr[i];
        int nc = now.c + dc[i];
        if (mapOut(nr, nc) || visited[nr][nc] == -1) continue;
        if (map[nr][nc] == 0) {
          visited[nr][nc] = -1;
          queue.add(new Node(nr, nc));
        } else {
          visited[nr][nc]++;
          if (visited[nr][nc] >= 2) {
            melt_list.add(new Node(nr, nc));
            visited[nr][nc] = -1;
          }
        }
      }
    }
    if (melt_list.isEmpty()) return false;
    while (!melt_list.isEmpty()) {
      Node now = melt_list.poll();
      map[now.r][now.c] = 0;
    }
    return true;
  }

  static boolean mapOut(int r, int c) {
    return (r < 0 || N <= r || c < 0 || M <= c);
  }
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!