[BOJ] (11967) 불켜기 (Java)

(11967) 불켜기 (Java)

문제

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

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

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

입력

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

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

출력

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

예제 입력 1

3 6
1 1 1 2
2 1 2 2
1 1 1 3
2 3 3 1
1 3 1 2
1 3 2 1

예제 출력 1

5

힌트

(1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으므로, (2, 3)위치에 있는 스위치는 누를 수 없다. 그러므로 불을 밝힐 수 있는 방의 최대 개수는 5이다.

출처

Olympiad > USA Computing Olympiad > 2015-2016 Season > USACO December 2015 Contest > Silver 1번

데이터를 추가한 사람: BaaaaaaaaaaarkingDog, bjh3502
문제를 번역한 사람: sheong_2

알고리즘 분류

그래프 이론
그래프 탐색
너비 우선 탐색

Solution

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static int n, m, cnt;
    public static class Node {
        int x, y;
        Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public static boolean[][] visited;
    public static boolean[][] lightOn;
    public static boolean[][] ableRoom;
    public static Queue<Node> q;
    public static ArrayList<Node>[][] barn;
    public static int[] dx = {-1, 1, 0, 0};
    public static int[] dy = {0, 0, -1, 1};

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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        visited = new boolean[n][n];
        lightOn = new boolean[n][n];    // 불이 켜져있는지 체크
        ableRoom = new boolean[n][n];   // 탐색했던 방의 인접 칸인 경우, 방문 불이 켜진다면 가능한 방임
        q = new LinkedList<Node>();
        cnt = 0;

        // 헛간 세팅
        barn = new ArrayList[n][n];     // 방안에 여러개의 스위치가 있을 수 있으므로 리스트형 배열로 선언
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                barn[i][j] = new ArrayList<Node>();
            }
        }

        // 각 방 별로 스위치 정보 입력
        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 sx = Integer.parseInt(st.nextToken());
            int sy = Integer.parseInt(st.nextToken());
            barn[x-1][y-1].add(new Node(sx-1, sy-1));
        }

        // 큐 초기 세팅
        q.offer(new Node(0, 0));
        visited[0][0] = true;
        lightOn[0][0] = true;
        cnt++;

        findSwitch();
        bw.write(String.valueOf(cnt));
        bw.flush();
        bw.close();
        br.close();
    }

    public static void findSwitch() {
        while(!q.isEmpty()) {
            Node cur = q.poll();

            // 방문가능한 방 체크하기
            for(int k = 0; k < 4; k++) {
                int nx = cur.x + dx[k];
                int ny = cur.y + dy[k];

                // 헛간의 범위를 벗어나는 경우 skip
                if(isNotRange(nx, ny)) continue;

                // 헛간의 범위를 벗어나지 않는 경우, 불이 켜져있기만 하다면 방문이 가능해지므로 방문 가능한 방으로 체크
                ableRoom[nx][ny] = true;
            }

            // 현재 방에서 불은 켤 수 있는 방의 불 전부 켜기
            for(int k = 0; k < barn[cur.x][cur.y].size(); k++) {
                Node tmp = barn[cur.x][cur.y].get(k);
                if(!lightOn[tmp.x][tmp.y]) {
                    lightOn[tmp.x][tmp.y] = true;
                    cnt++;
                }

                // 방문 가능한 방이고, 아직 방문한 적이 없다면 큐에 넣고 방문 처리
                if(ableRoom[tmp.x][tmp.y] && !visited[tmp.x][tmp.y]) {
                    q.offer(new Node(tmp.x, tmp.y));
                    visited[tmp.x][tmp.y] = true;
                }
            }

            // 인접 방 탐색
            for(int k = 0; k < 4; k++) {
                int nx = cur.x + dx[k];
                int ny = cur.y + dy[k];

                // 헛간의 범위를 벗어나거나, 이미 방문한 방이거나, 불이 꺼져있는 방이거나, 방문 불가능한 방인 경우 skip
                if(isNotRange(nx, ny) || visited[nx][ny] || !lightOn[nx][ny] || !ableRoom[nx][ny]) continue;

                q.offer(new Node(nx, ny));
                visited[nx][ny] = true;

            }
        }
    }

    public static boolean isNotRange(int x, int y) {
        return (x < 0 || x >= n || y < 0 || y >= n) ? true : false;
    }
}

Feedback

어떤 방에 방문하였을 때, 인접한 방들은 언제든 불만 켜져있다면 방문이 가능한 방이다.

예제 입력 1에서 첫 (1, 1) 방문 시에는 인접 방인 (2, 1)에 불이 켜져있지 않아 방문하지 못한다. 하지만 이후 (1, 3)에 방문 시 방 (2, 1)의 불을 켤 수 있으므로, 방문할 수 있게된다. 하지만 큐의 탐색 과정에서 이미 (1, 1)은 탐색을 마쳤기 때문에 순리대로라면 (2, 1)은 이미 큐에 담길 기회를 잃은 셈이다. 하지만 (2, 1)은 방문할 수 있는 방이 맞고, 방문하여야만 방 (2, 2)의 불을 켤 수 있게 된다.

따라서 이 문제에서는 방 (1, 1) 부터 시작하여, 탐색 과정에서 그 인접 칸들은 모두 방문 가능한 방이라는 사실을 저장해두었다가, 인접 칸 탐색과 함께 방문 가능한 방의 탐색을 할 수 있도록 해주어야 한다.