Algorithm

백준[2638] - 치즈

  • 문제: https://www.acmicpc.net/problem/2638
  • 분류: 그래프탐색, DFS
  • 난이도: G3
  • 소요시간: 20m
  • 자아성찰:
    • DFS, BFS 등 그래프 탐색을 활용한 풀이가 필요한 문제.
    • "치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 간주한다" 를 어떻게 판단할지 고민
      • 치즈 내부 공간임을 어떻게 판단할것인가?
    • "모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다" 문장에서 감을 잡았다.
      • 0,0부터 DFS를 통해 거쳐갈 수 있는 모든 칸은 외부 공기로 마킹한다.
    • 매 time마다 0,0부터 DFS를 통해 외부 공기를 마킹한 후 -> 다시 map을 돌며 각 위치한 치즈에 대해 4방향 외부공기 확인 (4방향에 마킹된 칸 >= 2일 경우 치즈 녹임)

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

public class B_2638 {

    static int N, M, cheese = 0, time = 0;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int[][] map;

    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];
        // map
        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());
                if (map[i][j] == 1) {
                    map[i][j] = -1; // 임의로 치즈는 -1로 설정 (time에서 1 사용 예정)
                    cheese++;
                }
            }
        }

        // 치즈가 모두 녹을때까지 반복
        while (cheese > 0) {
            time++;
            marking(time, 0, 0); // 0,0부터 외부공기 time으로 마킹
            meltCheese(); // 치즈 녹이러 출발
        }
        System.out.println(time);
    }

    public static void marking(int time, int x, int y) {
        map[x][y] = time; // 외부공기 마킹
        for (int n = 0; n < 4; n++) {
            int nx = x + dx[n];
            int ny = y + dy[n];
            if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue; // 맵 벗어나는 경우 스킵
            if (map[nx][ny] == time || map[nx][ny] == -1) continue; // 이미 방문 or 치즈인 경우 스킵
            marking(time, nx, ny); // 외부공기 마킹하러 이동
        }
    }

    public static void meltCheese() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != -1) continue; // 치즈 아닌경우 스킵
                int airCount = 0; // 현재 치즈에 닿은 외부공기 count
                for (int n = 0; n < 4; n++) {
                    int nx = i + dx[n];
                    int ny = j + dy[n];
                    if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue; // 맵 벗어나는 경우 스킵
                    if (map[nx][ny] > 0) airCount++; // 외부공기 카운트 (0 == 외부공기 X / -1 == 치즈 / > 0 == 외부공기)
                }
                // 외부공기 2칸 이상 닿은 경우
                if (airCount >= 2) {
                    cheese--; // 치즈 녹음
                    map[i][j] = 0; // 외부공기 닿지 않은 빈칸 처리
                }
            }
        }
    }
}

'Algorithm' 카테고리의 다른 글

백준[15661] - 링크와 스타트  (0) 2024.05.27
백준[2529] - 부등호  (0) 2024.05.22
백준[2583] - 영역 구하기  (0) 2024.05.15
백준[2012] - 등수 매기기  (0) 2024.05.13
백준[11509] - 풍선 맞추기  (1) 2024.04.18