백준 11967번: 불켜기 (JAVA)

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

11967번: 불켜기

문제

농부 존은 최근에 N × N개의 방이 있는 거대한 헛간을 새로 지었다. 각 방은 (1, 1)부터 (N,N)까지 번호가 매겨져있다(2 ≤ N ≤ 100). 어둠을 무서워하는 암소 베시는 최대한 많은 방에 불을 밝히고 싶어한다.

베시는 유일하게 불이 켜져있는 방인 (1, 1)방에서 출발한다. 어떤 방에는 다른 방의 불을 끄고 켤 수 있는 스위치가 달려있다. 예를 들어, (1, 1)방에 있는 스위치로 (1, 2)방의 불을 끄고 켤 수 있다. 베시는 불이 켜져있는 방으로만 들어갈 수 있고, 각 방에서는 상하좌우에 인접한 방으로 움직일 수 있다. 

베시가 불을 켤 수 있는 방의 최대 개수를 구하시오.

입력

첫 번째 줄에는 N(2 ≤ N ≤ 1 00)과, M(1 ≤ M ≤ 20,000)이 정수로 주어진다.

다음 M줄에는 네 개의 정수 x, y, a, b가 주어진다. (x, y)방에서 (a, b)방의 불을 켜고 끌 수 있다는 의미이다. 한 방에 여러개의 스위치가 있을 수 있고, 하나의 불을 조절하는 스위치 역시 여러개 있을 수 있다. 

출력

베시가 불을 켤 수 있는 방의 최대 개수를 출력하시오.

 

---

 

풀이

BFS 응용 문제 중 하나이다. 특별히 어렵진 않았다.

 

배운 점

1. f(x, y) = List of (x_i, y_i)를 저장할 때, 좌표를 int로 변환하여 Map(int, List<Integer>)로 저장하면 된다.

2. 문제를 풀고, 다른 사람의 코드를 보는데, 'xiaowuc1'도 단위 기능마다 주석을 달아놓은 걸 봤다. '내가 뭐라고 주석 안 달고 깝치나'라는 생각이 들어, 기능마다 주석을 달기로 마음먹었다. 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 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());
        // {스위치의 좌표, 켜지는 장소의 좌표}를 저장한다.
        HashMap<Integer, List<Integer>> hMap = new HashMap<>();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int button = (Integer.parseInt(st.nextToken()) - 1) * N + (Integer.parseInt(st.nextToken()) - 1); 
            int light = (Integer.parseInt(st.nextToken()) - 1) * N + (Integer.parseInt(st.nextToken()) - 1);
            if (hMap.containsKey(button)) {
                hMap.get(button).add(light);
            }
            else {
                hMap.put(button, new ArrayList<Integer>());
                hMap.get(button).add(light);
            }
        }

        int[][] map = new int[N][N];
        map[0][0] = 1;
        boolean[][] visited = new boolean[N][N];
        visited[0][0] = true;
        int ans = 1;
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[] {0, 0});
        while (!queue.isEmpty()) {
            int[] temp = queue.poll();
            int r = temp[0], c = temp[1];
            int loc = r*N + c;
            // 해당 위치에 스위치가 있다면 불 키기
            if (hMap.containsKey(loc)) {
                for (int light: hMap.get(loc)) {
                    int x = light / N;
                    int y = light % N;
                    if (map[x][y] == 0) {
                        map[x][y] = 1;
                        ans++;
                        for (int i = 0; i < 4; i++) {
                            int nx = x + dr[i], ny = y + dc[i];
                            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
                            if (!visited[nx][ny]) continue;
                            // 방문한 곳중 새로 불 켜진 곳 근처를 다시 방문한다.
                            // 그 곳에서만 새로 불 켜진 곳에 갈 수 있으며,
                            // 만약 현재 갈 수 있음에도 방문하지 않았다면 나중에라도 BFS로 방문하게 된다.
                            queue.offer(new int[] {nx, ny});
                        }
                    }
                }
            }
            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i], nc = c + dc[i];
                if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
                if (visited[nr][nc] || map[nr][nc] == 0) continue;
                visited[nr][nc] = true;
                queue.offer(new int[] {nr, nc});
            }
        }
        System.out.println(ans);
    }

}