[Baekjoon] 백준 2638 치즈 (G3 / BFS) - Java

링크

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

2638번: 치즈

 

 

 

 

문제 해석

N*M 모눈종이

치즈의 4변 중에서 2변 이상이 공기와 접촉하는 경우 1시간 후 없어짐
치즈 내부에 있는 공간은 치즈 외부의 공기와 접촉하지 않는 것으로 가정함
모눈종이의 가장 가장자리에는 치즈가 놓이지 않는 것으로 가정
치즈가 모두 녹아 없어지는데 걸리는 시간을 구하는 프로그램


- 입력
첫 번째 줄 : N M
  N : 세로 격자 수 
  M : 가로 격자 수

- N개 줄 : 치즈 및 공기


- 출력
치즈가 모두 녹아 없어지는데 걸린 시간

 

 

 

 

풀이 & 코드 해석

문제에서 고려해야할 가장 큰 사항은 치즈 바깥의 공기(0)와 안쪽의 공기(0)가 서로 다르다는 것입니다.

 

따라서 바깥쪽 공기와 안쪽 공기가 서로 다른 것을 표시하기 위해서 BFS를 통해 바깥 공기를 모두 다른 임의의 숫자(9)로 변경해 주었습니다.

 

 

이후 치즈(1)를 찾아서 해당 치즈에 인접한 바깥 공기(9)가 2개 이상인지를 체크하여 0으로 값을 바꿔주는 과정을 반복하면 됩니다.

 

이때 바깥 공기와 인접하다고 해서 치즈를 바로 0으로 바꿔버리면 바로 주변에 인접한 치즈가 바깥 공기에 맞닿아 있다고 생각할 수 있기 때문에 임의의 값(-1)으로 변경해주었고, 마지막에 한 번에 변경하였습니다.

(아마 바깥 공기를 임의의 수(-9)로 변경해주었기 때문에 산화될 치즈를 -1로 바꿔줄 필요는 없습니다.)

 

 

 

코드

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

public class 치즈 {

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

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

        // 첫 번째 줄
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int 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());
            }
        }

        // print();

        int answer = 0;
        while (true) {
            answer++;
            int count = 0;

            // 바깥쪽 공기만 체크
            bfsZero(0, 0);

            // 한번도 검사하지 않은 치즈에 대해서 이어진 치즈 검사
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (map[i][j] == 1) {
                        count++;
                        bfs(i, j);
                    }
                }
            }

            // map을 0과 1로만 다시 표현
            if (count != 0) {
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < M; j++) {
                        if (map[i][j] == -1) {
                            map[i][j] = 0;
                        } else if (map[i][j] == 2) {
                            map[i][j] = 1;
                        } else if (map[i][j] == -9) {
                            map[i][j] = 0;
                        }
                    }
                }
            } else {
                answer--;
                break;
            }
        }

        System.out.println(answer);
    }


    static class Point {
        int r;
        int c;

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

    static void bfsZero(int i, int j) {
        Queue<Point> q = new LinkedList<>();
        q.offer(new Point(i, j));
        map[i][j] = -9;

        while (!q.isEmpty()) {
            Point p = q.poll();

            for (int d = 0; d < dr.length; d++) {
                int nr = p.r + dr[d];
                int nc = p.c + dc[d];

                if (nr >= 0 && nr < map.length && nc >= 0 && nc < map[0].length && map[nr][nc] == 0) {
                    map[nr][nc] = -9;
                    q.offer(new Point(nr, nc));
                }
            }
        }
    }


    static void bfs(int i, int j) {
        Queue<Point> q = new LinkedList<>();
        q.offer(new Point(i, j));
        map[i][j] = 2;

        while (!q.isEmpty()) {
            Point p = q.poll();

            int zeroCount = 0;
            for (int d = 0; d < dr.length; d++) {
                int nr = p.r + dr[d];
                int nc = p.c + dc[d];

                if (map[nr][nc] == -9) {
                    zeroCount++;
                }
                if (map[nr][nc] == 1) {
                    q.offer(new Point(nr, nc));
                    map[nr][nc] = 2;
                }
            }
            if (zeroCount >= 2) {
                map[p.r][p.c] = -1;
            }
        }
    }


    static void print() {
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }

    }
}

 

 

 

 

발생한 문제 & 해결 방안

처음 문제를 제출하였을 때 바깥쪽 공기와 안쪽 공기를 따로 만들어야 한다는 생각없이 무지성으로 풀어서 틀린 후 다시 코드를 수정하였다.

피곤하더라도 문제는 꼼꼼히 읽어보고 풀자!

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java