[백준] 11967번 - 불켜기 [Java]

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

 

[백준] 11967번 - 불켜기 [Java]

[백준] 11967번 - 불켜기 [Java]

---

1.  아이디어

 

스위치가 있는 방에 방문해서 불을 켰을 때 불이 켜지게 된 방이 과거에 방문할 수 있었던 방이면 방문을 해야하는 문제이다. 이를 위해 현재 불이 꺼져있지만 방문할 수 있었던 방에 대한 방문체크를 별도로 진행해서 불을 켰을 때 해당 방이 이전에 방문할 수 있었던 방이면 방문할 수 있도록 했다.

---

2. 문제풀이

 

특정 방에 여러 개의 스위치가 존재할 수 있는 상황으로 리스트를 받는 2차원 배열로 입력을 처리했다. BFS에서 변수로 불이 켜진 상태를 표시하는 원본 맵인 boolean 타입 2차원 배열과 실제 방문, 임시 방문을 담당하는 방문 체크 배열을 사용했다. 로직은 현재 방에 스위치가 있으면 불을 켜고 불을 킨 방이 임시 방문을 한 적이 있으면 Queue에 담는다. 현재 방에 대한 사방탐색은 불이 켜져있으면 그냥 하고 불이 꺼져있으면 임시 방문 체크를 한다.

---

3. 코드

 

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

public class Main {

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

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        List<int[]>[][] lightMap = new ArrayList[1 + N][1 + N];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                lightMap[i][j] = new ArrayList<>();
            }
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            lightMap[x][y].add(new int[]{a, b});
        }

        boolean[][] map = new boolean[1 + N][1 + N];
        map[1][1] = true;

        // 스위치를 누른적이 있는지 판단하는 flag로 스위치를 시작점에서 스위치를 더 누를 수 없어질 때까지 반복
        boolean isChanged = true;
        while (isChanged) {
            isChanged = bfs(N, lightMap, map);
        }

        int cnt = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (map[i][j]) cnt++;
            }
        }

        System.out.println(cnt);
    }

    private static boolean bfs(int N, List<int[]>[][] lightMap, boolean[][] map) {
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{1, 1});

        boolean[][] visited = new boolean[1 + N][1 + N];
        visited[1][1] = true;

        while (!q.isEmpty()) {
            int[] node = q.remove();

            // 스위치가 있는 방에 도달하면 스위치를 전부 켜고 true 반환, 켠 스위치를 다시 켜지 않도록 리스트 초기화
            if (!lightMap[node[0]][node[1]].isEmpty()) {
                for (int[] light : lightMap[node[0]][node[1]]) {
                    map[light[0]][light[1]] = true;
                }
                lightMap[node[0]][node[1]].clear();
                return true;
            }

            for (int dir = 0; dir < 4; dir++) {
                int nr = node[0] + dr[dir];
                int nc = node[1] + dc[dir];

                if (nr < 1 || nr > N || nc < 1 || nc > N) continue;
                if (!map[nr][nc] || visited[nr][nc]) continue;

                q.add(new int[]{nr, nc});
                visited[nr][nc] = true;
            }
        }

        return false;
    }

}

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

public class Main {

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

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        List<int[]>[][] lightMap = new ArrayList[1 + N][1 + N];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                lightMap[i][j] = new ArrayList<>();
            }
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            lightMap[x][y].add(new int[]{a, b});
        }

        int cnt = bfs(N, lightMap);
        System.out.println(cnt);
    }

    private static int bfs(int N, List<int[]>[][] lightMap) {
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{1, 1});

        boolean[][] map = new boolean[1 + N][1 + N];
        map[1][1] = true;

        // 불은 켠 방에 대한 방문체크
        boolean[][] visited = new boolean[1 + N][1 + N];
        visited[1][1] = true;

        // 불이 꺼져있었지만 방문할 수 있었던 방에 대한 방문체크
        boolean[][] tmpVisited = new boolean[1 + N][1 + N];

        while (!q.isEmpty()) {
            int[] node = q.remove();

            // 스위치가 있는 방이면 스위치를 켜고 불이 꺼져있었지만 방문할 수 있었던 방이면 방문 진행
            for (int[] light : lightMap[node[0]][node[1]]) {
                if (map[light[0]][light[1]]) continue;

                map[light[0]][light[1]] = true;

                if (tmpVisited[light[0]][light[1]]) {
                    q.add(new int[]{light[0], light[1]});
                    visited[light[0]][light[1]] = true;
                    tmpVisited[light[0]][light[1]] = false;
                }
            }

            for (int dir = 0; dir < 4; dir++) {
                int nr = node[0] + dr[dir];
                int nc = node[1] + dc[dir];

                if (nr < 1 || nr > N || nc < 1 || nc > N) continue;
                if (visited[nr][nc]) continue;

                // 불이 켜진 방이면 방문하고 불이 꺼진 방이면 방문할 수 있었던 방으로 방문체크
                if (map[nr][nc]) {
                    q.add(new int[]{nr, nc});
                    visited[nr][nc] = true;
                    tmpVisited[nr][nc] = false;
                } else {
                    tmpVisited[nr][nc] = true;
                }
            }
        }

        int cnt = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (map[i][j]) cnt++;
            }
        }

        return cnt;
    }

}

---

4. 후기

 

- BFS(반복 탐색 진행)

- BFS(1번 탐색 진행)