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

onAuspicious·2021년 12월 18일

Algorithm

목록 보기

20/24

문제

농부 존은 최근에 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)방의 불을 켜고 끌 수 있다는 의미이다. 한 방에 여러개의 스위치가 있을 수 있고, 하나의 불을 조절하는 스위치 역시 여러개 있을 수 있다.

출력

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

접근 방법

문제의 요구사항을 보면 전형적인 BFS 문제와 유사합니다. 하지만 한 가지 고려해야 할 점이 있습니다. 바로 이미 지나왔던 위치가 불이 켜져서 기존에는 방문할 수 없었지만 이제 접근이 가능하게 된 경우입니다.
그렇다면 어떻게 처리할 수 있을까요? 두 단계로 분리해서 접근해 봅시다.

(1, 1)로부터 상, 하, 좌, 우로 움직여 갈 수 있는 모든 위치를 찾는 기존의 BFS 로직
현재 위치에서 가능한 모든 불을 켜는 로직

우리는 2번에서 베시가 움직일 수 있는 모든 공간을 찾아나가면서 해당 위치에서 아직 켜지지 않은 스위치가 있을때 스위치를 켜고 다시 한번 2번을 반복해나가면 됩니다. 그러다가 넓혀진 모든 공간에서 스위치를 킬 수 있는 경우가 한개도 없다면 그때가 우리가 원하는 결과일 것입니다.
해당 문제에서 위와 같은 상황을 구현하기 위해 재귀를 사용했습니다. 아래 코드를 보시면 bfs() 함수에서 isSwitchOn 이라는 boolean 타입의 변수를 볼 수 있습니다. 현재 상황에서 스위치로 불을 킬 수 있는 경우가 있다면 isSwitchOn이 true 가 되면서 다시 한 번 bfs()를 호출하게 됩니다.
출력시에 기존의 (1, 1)은 항상 켜져있음에 유의해야 합니다. 결과값에 + 1을 더해주어 출력해줍시다.
문제를 풀이해 나가며 한가지 의문이 생길 수 있습니다. bfs()를 호출할 때마다 우리는 기존에 방문했던 위치를 담은 배열 boolean visit[][] 을 새롭게 생성해 주어야 합니다. 때문에 문제에서도 512MB라는 큰 메모리로 주어집니다. 그렇다면 항상 새롭게 배열을 만들어 줄 때와 java의 Arrays에서 지원하는 fill() 메서드를 사용해 초기화 해줄때 어떠한 성능상의 차이가 있을지 생각할 수 있습니다. 결과는 아래에 남겨두었습니다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;

public class TurnOnTheLight {

    static int n, m;
    static ArrayList<Node>[][] graph;
    static int[] dx = new int[]{-1, 0, 1, 0};
    static int[] dy = new int[]{0, 1, 0, -1};
    static boolean[][] visit;
    static boolean[][] lights;


    static class Node {
        int x;
        int y;

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);

        lights = new boolean[n + 1][n + 1];
        graph = new ArrayList[n + 1][n + 1];
        lights[1][1] = true;

        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++) {
            input = br.readLine().split(" ");
            graph[Integer.parseInt(input[0])][Integer.parseInt(input[1])].add(new Node(Integer.parseInt(input[2]), Integer.parseInt(input[3])));
        }

        System.out.println(bfs() + 1);
        br.close();
    }

    public static int bfs() {
        int cnt = 0;
        ArrayDeque<Node> dq = new ArrayDeque<>();
        dq.offerLast(new Node(1, 1));
        visit = new boolean[n + 1][n + 1];

        boolean isSwitchOn = false;

        while (!dq.isEmpty()) {
            Node now = dq.removeFirst();

            for (int i = 0; i < 4; i++) {
                int tmpx = now.x + dx[i];
                int tmpy = now.y + dy[i];
                if (0 <= tmpx && tmpx <= n && 0 <= tmpy && tmpy <= n && !visit[tmpx][tmpy] && lights[tmpx][tmpy]) {
                    dq.offerLast(new Node(tmpx, tmpy));
                    visit[tmpx][tmpy] = true;
                }
            }

            for (Node turnOn : graph[now.x][now.y]) {
                if (!lights[turnOn.x][turnOn.y]) {
                    isSwitchOn = true;
                    lights[turnOn.x][turnOn.y] = true;
                    cnt++;
                }
            }
        }

        if (isSwitchOn) {
            return cnt + bfs();
        }
        return cnt;
    }
}