[BaekJoon] 11967 불켜기 (Java)

1.  문제 링크

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

2.  문제

요약

• 존은 N x N개의 방이 있는 거대한 헛간을 새로 지었는데, 각 방은 (1, 1)부터 (N, N)까지 번호가 매겨져 있습니다.
• 베시는 최대한 많은 방에 불을 밝히고 싶어하는데, 유일하게 불이 켜져있는 방인 (1, 1) 방에서 출하고, 어떤 방에는 다른 방의 불을 끄고 켤 수 있는 스위치가 달려있습니다.
• 베시는 불이 켜져있는 방으로만 들어갈 수 있고, 각 방에서는 상하좌우에 인접한 방으로 움직일 수 있습니다.
• 베시가 불을 켤 수 있는 방의 최대 개수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 2보다 크거나 같고 100보다 작거나 같은 N과 1보다 크거나 같고 20,000보다 작거나 같은 M이 주어지고 두 번째 줄부터 M개의 줄에 네 개의 정수 x, y, a, b가 주어집니다. (x, y) 방에서 (a, b) 방의 불을 켜고 끌 수 있다는 의미입니다. 한 방에 여러 개의 스위치가 있을 수 있고, 하나의 불을 조절하는 스위치 역시 여러 개 있을 수 있습니다.
• 출력: 첫 번째 줄에 베시가 불을 켤 수 있는 방의 최대 개수를 출력합니다.

3.  소스코드

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

public class Main {
    static int N, M;
    static HashMap<Room, ArrayList<Room>> switches;
    static int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
    static boolean[][] lighted, visited;

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        M = scanner.nextInt();
        switches = new HashMap<>();

        for(int idx = 0; idx < M; idx++) {
            int x = scanner.nextInt(), y = scanner.nextInt();
            int a = scanner.nextInt(), b = scanner.nextInt();

            Room lightingRoom = new Room(x - 1, y - 1), lightedRoom = new Room(a - 1, b - 1);

            if(!switches.containsKey(lightingRoom)) switches.put(lightingRoom, new ArrayList<>());
            switches.get(lightingRoom).add(lightedRoom);
        }
    }

    static void solution() {
        lighted = new boolean[N][N];
        visited = new boolean[N][N];

        System.out.println(bfs(0, 0) + 1);
    }

    static int bfs(int x, int y) {
        int count = 0;
        Queue<Room> queue = new LinkedList<>();
        visited = new boolean[N][N];

        queue.offer(new Room(x, y));
        lighted[x][y] = true;
        visited[x][y] = true;

        boolean flag = false;
        while(!queue.isEmpty()) {
            Room cur = queue.poll();

            for(Room lightedRoom : switches.getOrDefault(cur, new ArrayList<>())) {
                if(!lighted[lightedRoom.x][lightedRoom.y]) {
                    lighted[lightedRoom.x][lightedRoom.y] = true;
                    count++;
                    flag = true;
                }
            }

            for(int dir = 0; dir < dx.length; dir++) {
                int cx = cur.x + dx[dir], cy = cur.y + dy[dir];

                if(isInMap(cx, cy)) {
                    if(lighted[cx][cy] && !visited[cx][cy]) {
                        visited[cx][cy] = true;
                        queue.offer(new Room(cx, cy));
                    }
                }
            }
        }

        if(flag) count += bfs(0, 0);

        return count;
    }

    static boolean isInMap(int x, int y) {
        if(x >= 0 && x < N && y >= 0 && y < N) return true;
        return false;
    }

    static class Room {
        int x, y;

        public Room(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Room room = (Room) o;
            return x == room.x && y == room.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 각 방을 나타내기 위해 Room 클래스를 정의합니다.
  • 각 방의 행 좌표를 나타내는 x, 열 좌표를 나타내는 y를 멤버 변수로 갖습니다.
  • HashMap에 Room 객체를 key로 넣을 것인데, key를 (x, y) 좌표를 통해 찾아내기 위해 equals 메서드와 hashCode 메서드를 오버라이딩합니다.

• 각 방에서 불을 끄고 켤 수 있는 방들을 나타내기 위해 HashMap을 생성하고 이를 통해 나타냅니다.
• 불이 켜진 방을 나타내기 위해 N x N 크기의 2차원 배열 lighted를 생성하고, BFS 탐색 시에 각 방을 방문하였는지 나타내기 위해 N x N 크기의 2차원 배열 visited를 생성합니다.
• BFS 탐색을 통해 베시가 불을 켤 수 있는 방의 최대 개수를 구합니다.
  • (0, 0) 방에만 불이 켜진 상태로 시작하기 때문에 (0, 0) 방을 탐색될 대상들을 담는 Queue에 담고 visited의 (0, 0) 위치를 방문 체크하며 불이 켜져있기 때문에 (0, 0)의 lighted 값을 true로 변경합니다.
  • Queue가 빌 때까지 Queue에서 방을 하나씩 빼면서 아래 작업을 수행합니다.
    • 현재 탐색하고 있는 방에서 끄고 켤 수 있는 방이 어디인지 살펴보고 아직 그 방들 중에 불이 안 켜진 방이 있다면 불을 켜고 불을 킨 방의 개수를 나타내는 count의 값을 1 증가시킵니다.
    • 모든 방에 대해 작업을 완료했다면 현재 탐색하고 있는 방의 인접한 방들을 살펴 N x N 안에 존재하고 불이 켜져있으며 아직 방문되지 않은 방들을 이후 탐색을 위해 Queue에 넣고 방문 체크를 합니다.
  • Queue가 모두 비워진 후에 BFS 탐색 동안 불이 켜진 방이 하나라도 존재한다면 재귀로 다시 (0, 0)부터 BFS 탐색을 하고 그 때의 count 값들을 누적해나갑니다.
    • 이 때, 각 BFS 탐색마다 방문 정보는 초기화되어야 하므로 visited는 초기화하고 불이 켜진 방에 대한 정보는 유지되어야하기 때문에 초기화하지 않습니다.
    • (0, 0)부터 BFS 탐색을 다시 하면서 불을 켤 수 있는 모든 방들에 대해 불을 켜는 작업을 합니다.
  • 반대로 BFS 탐색 동안 불이 켜진 방이 하나도 없다면, 베시가 불을 켤 수 있는 모든 방에 대해 불을 켰다는 의미가 되므로 그 때의 count 값을 반환합니다.
• BFS 탐색이 끝난 후에 반환된 count 값에 1을 더한 값이 정답이 됩니다.
  • (0, 0) 방에 대해서는 개수를 추가해주지 않았기 때문에 추가를 해준 것입니다.