[백준 11967번] 불켜기

문제 링크: 11967번 제목

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

 

이 문제에서, 구현을 어렵게 하는 케이스는 다음과 같은 경우이다.

위 예시의 경우 곧바로 알 수 있는 것은, ㄴ자 모양을 따라 쭉 불을 켜면서 이동하게 된다는 것이다. 그런데, (3, 4)에는 (4, 0)을 켜는 스위치가 있으며, 우리는 (3, 1) 또한 방문하기 때문에 (4, 0) 또한 방문해야 한다. 하지만 단순 BFS로 문제를 해결하고자 한다면 이미 불이 켜지지 않아 방문할 수 없는 방으로 처리되고 만다.

 

이를 해결하기 위해서는... 첫 번째로 다음과 같은 무식한? 무지막지한? 방법을 사용할 수 있다. 계속해서 (0, 0)에서 출발해서 BFS를 돌리면서, 이전 탐색과 현재 탐색에서 방문하는 방의 개수가 같다면 더 이상 추가로 방문할 수 있는 방이 생길 수 없다는 것을 의미하므로, 그 때에 최종적으로 탐색을 종료하고 불이 켜진 방의 개수를 센다. 하지만 이는 상식적으로도 꽤나 비효율적인데, 이미 처리되었던 방을 또다시 처리하고 나서야 문제가 되는 방을 큐에서 빼내게 되기 때문이다. 실제로도 다음 도표에서 아래가 개선 이전, 위가 개선 이후의 실행 결과로서 어느 정도는 유의미한 차이가 있는 것으로 보인다.

 

 

그렇다면 이를 어떻게 개선해야 할까?

위 예시를 조금 다르게 해서 다음과 같은 예시를 생각해볼 수 있다.

여기서 (4, 0)의 경우 불은 켜지지만, 결코 방문될 수는 없는 곳이다.

 

이를 설명하자면 다음과 같다.

불이 켜질 것이지만 아직 켜지지 않은 방 A가 있다고 하자.

이 방의 경우, 불이 켜진 후에 A와 인접한 방을 방문하면 아무런 문제가 되지 않는다.

하지만, 불이 켜지기 이전에 A와 인접한 방을 방문하면 문제가 된다.

 

즉,

① A의 불이 켜지기 이전에,

② A와 인접한 방을 방문했으면서,

③ 해당 방의 불이 차후에 켜진다면,

해당 방은 이후에 재방문되어야 하는 방이다.

따라서 BFS 탐색을 하면서 이 방을 큐에 바로 넣어주면 되는 것이다.

 

import java.io.*;
import java.util.*;
import static java.lang.Integer.parseInt;

class Pos {
    int r;
    int c;

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

public class Main {
    static int[] dr = {0, 0, 1, -1};
    static int[] dc = {1, -1, 0, 0};
    static int n;
    static int m;
    static boolean[][] light = new boolean[100][100];
    static boolean[][] candid = new boolean[100][100];
    static List<Pos>[][] graph = new ArrayList[100][100];

    public static void main(String[] args) throws IOException {
        input();

        light[0][0] = true;
        Queue<Pos> q = new LinkedList<>();

        boolean[][] visit = new boolean[n][n];
        q.offer(new Pos(0, 0));
        while (!q.isEmpty()) {
            Pos curr = q.poll();
            for (Pos adj : graph[curr.r][curr.c]) {
                if (!light[adj.r][adj.c] && candid[adj.r][adj.c]) q.offer(new Pos(adj.r, adj.c));
                light[adj.r][adj.c] = true;
            }
            for (int d = 0; d < 4; d++) {
                int nr = curr.r + dr[d];
                int nc = curr.c + dc[d];
                if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
                candid[nr][nc] = true;
                if (visit[nr][nc]) continue;
                if (!light[nr][nc]) continue;
                visit[nr][nc] = true;
                q.offer(new Pos(nr, nc));
            }
        }

        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (light[i][j]) {
                    cnt++;
                }
            }
        }
        System.out.println(cnt);
    }

    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = parseInt(st.nextToken());
        m = parseInt(st.nextToken());
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) graph[i][j] = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int r1 = parseInt(st.nextToken()) - 1;
            int c1 = parseInt(st.nextToken()) - 1;
            int r2 = parseInt(st.nextToken()) - 1;
            int c2 = parseInt(st.nextToken()) - 1;
            graph[r1][c1].add(new Pos(r2, c2));
        }
    }
}