[백준] no2638:치즈 - BFS, DFS

문제

N x M 크기의 맵에 공기는 0, 치즈는 1로 주어진다.

조건 1. 맵의 최외각은  항상 0이다.

조건 2. 치즈는 2면의 공기가 닿으면 1시간 안에 녹는다.

조건 3. 공기는 치즈 외부의 0에만 존재한다. (치즈로 사면이 둘러쌓인 공간의 0은 공기가 아니다.

---

원리

1. 1턴(1시간)에 한 번씩 맵을 순회한다.

2. 순회 중 외부 공기면, 사방향 탐색 진행(방문한 공기좌표는 방문체크 후 재방문 차단)

3. 순회 중 처음 방문한 치즈면, 방문체크만 함.

4. 순회 중 두번째 방문한 치즈면, 녹여버림.

5. 이 과정에서 치즈의 외각에서 별다른 사방향 탐색이 진행되지 않으므로, 내부 치즈는 탐색을 하지 않게됨.

6. 마찬가지로 치즈 내부 빈공간도 탐색하지 않게됨.

7. 만약 외부공기가 유입되는 경우는, 곧 치즈가 없는 구역에 대한 공기 탐색이 이루어 짐

8. 한 번이라도 치즈를 녹였다는게 체크되면, 1시간 지났음을 체크

9. 만약 탐색을 마치고 치즈를 녹인적이 없다면, 반복 종료.

---

나의 코드

[실패] 원인 : 2개 이상의 변이 닿아야 치즈가 녹는다는 조건을 깜빡함

즉, 이 코드는 한 변만 외부공기에 닿아도 녹는 코드임

public class no2638 {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static int N, M, Hours;
    private static int[][] map;
    private static boolean[][] visited;
    private static StringTokenizer st;
    private static int[] ver = {-1, 1, 0, 0};
    private static int[] hor = {0, 0 ,-1, 1};

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine(), " ");
        N= Integer.parseInt(st.nextToken());
        M= Integer.parseInt(st.nextToken());
        map = new int[N][M];
        Hours = 0;

        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());
        }

        while(true) {
            if(BFS()) Hours++;
            else break;
        }

        System.out.println(Hours);
    }

    private static boolean BFS() {
        Deque<Node> dq = new ArrayDeque<>();
        visited = new boolean[N][M];
        dq.add(new Node(0,0));
        boolean exist = false;

        while(!dq.isEmpty()) {
            Node now = dq.poll();

            for(int move=0; move<4 ; move++) {
                int nextY = now.Y + ver[move];
                int nextX = now.X + hor[move];

                if(nextY < 0 || nextX < 0 || nextY >= N || nextX >= M) continue; // 범위 넘어가면 패스
                if(visited[nextY][nextX]) continue; // 이미 이번 탐색때 방문한 좌표인 경우 패스

                if(map[nextY][nextX]==1) {
                    visited[nextY][nextX] = true; // 치즈 가장자리를 방문체크함으로서 재탐색을 막으며, 내부 공기는 아예 탐색자체를 막음
                    map[nextY][nextX] = 0; // 처음 온 치즈 가장자리는 녹임 (만약 내부 공기인 경우엔 외부에 치즈가 있으므로 방문 자체가 막힘)
                    exist = true;
                } else { // 방문한 적 없는 외부 공기인 경우
                    visited[nextY][nextX] = true;
                    dq.add(new Node(nextY, nextX)); // 인근의 다른칸을 탐색
                }
            }
        }

        return exist; // 이번 탐색에서 치즈가 존재했는지 리턴
    }

    private static class Node {
        private int Y, X;
        public Node(int y, int x) {
            this.Y = y;
            this.X = x;
        }
    }
}

 

[성공] BFS를 이용한 탐색 (2면 인접 조건 달성)

public class no2638 {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int N, M, Hours;
    private static int[][] map;
    private static boolean[][] visited;
    private static StringTokenizer st;
    private static int[] ver = {-1, 1, 0, 0};
    private static int[] hor = {0, 0 ,-1, 1};

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine(), " ");
        N= Integer.parseInt(st.nextToken());
        M= Integer.parseInt(st.nextToken());
        map = new int[N][M];
        Hours = 0;

        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());
        }

        while(true) {
            if(BFS()) Hours++;
            else break;
        }

        System.out.println(Hours);
    }

    private static boolean BFS() {
        Deque<Node> dq = new ArrayDeque<>();
        visited = new boolean[N][M];
        dq.add(new Node(0,0));
        boolean exist = false;

        while(!dq.isEmpty()) {
            Node now = dq.poll();

            for(int move=0; move<4 ; move++) {
                int nextY = now.Y + ver[move];
                int nextX = now.X + hor[move];

                /*
                 1. 치즈의 경우, visited인데 재방문이면 map에서 녹여주는 과정 필요
                 2. 공기의 경우, visited면 바로 패스
                 */

                if(nextY < 0 || nextX < 0 || nextY >= N || nextX >= M) continue; // 범위 넘어가면 패스
               
                // 공기든 치즈든 방문한 적이 있을 때, 
                if(visited[nextY][nextX]) {
                    if(map[nextY][nextX]==0) continue; // 이미 방문한 공기는 탐색 X
                    else {  // 한 면에 이미 공기가 닿은 치즈인 경우
                        map[nextY][nextX] = 0; // 치즈 녹여주고
                        exist = true;  // 이번 탐색에서 치즈 녹인 전적이 있음을 체크
                        continue;  // *아래 코드를 실행하지 못하도록 필수로 넣어줘야 함*
                    }
                }

                if(map[nextY][nextX]==1) visited[nextY][nextX] = true; // 치즈 가장자리를 방문체크함으로서 재탐색을 막으며, 내부 공기는 아예 탐색자체를 막음
                else { // 방문한 적 없는 외부 공기인 경우
                    visited[nextY][nextX] = true;
                    dq.add(new Node(nextY, nextX)); // 인근의 다른 칸을 탐색
                }
            }
        }

        return exist; // 이번 탐색에서 치즈를 녹였는지 여부를 리턴 : 하나라도 녹였으면 시간 + 1 해줘야 하므로 
    }

    private static class Node {
        private int Y, X;
        public Node(int y, int x) {
            this.Y = y;
            this.X = x;
        }
    }
}

---

레퍼런스 및 회고

레퍼런스 참고링크 : https://minhamina.tistory.com/156

1. DFS를 이용한 탐색 레퍼런스 코드

// dfs로 외부와 접촉한 공기 2로 표시
static void dfs(int x, int y) {
	visited[x][y] = true;
	map[x][y] = 2; // 외부 공기라는 의미로 2로 바꿔줌 

	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];

		if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
		if (visited[nx][ny] || map[nx][ny] == 1) continue;

		dfs(nx, ny); // 공기인 경우만 dfs 수행 
	}
}

2. BFS를 이용한 탐색 레퍼런스 코드

// bfs로 외부와 접촉한 공기 2로 표시
public static void bfs() {
	Queue<Point> queue = new LinkedList<>();
	queue.add(new Point(0, 0));
	visited[0][0] = true;
	map[0][0] = 2;

	while(!queue.isEmpty()) {
		int x = queue.peek().x;
		int y = queue.poll().y;

		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
			if (visited[nx][ny] || map[nx][ny] == 1) continue; 

			map[nx][ny] = 2; // 외부 공기라는 의미로 2로 바꿔줌 
			queue.add(new Point(nx, ny)); // 공기인 경우만 큐에 넣어줌
			visited[nx][ny] = true;
		}
	}
}

---

회고

1. 바둑 알고리즘과 유사하다

2. 현재는 각 턴당(시간당) 맵 전체를 탐색하게 되는데, 이는 비효율적일 수 있다.

따라서, 기존에 탐색했던 외부 공기층(0) 중 직전에 녹은 부분에 대해서만 탐색하는 BFS를 구현하면 메모리를 절약할 수 있을것이다.