[JAVA] BOJ 백준 11967번 - 불켜기

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

11967번: 불켜기

---

2. 내가 푼 방법

현재 위치에서 불을 켠 후 이동할 수 있는 곳을 BFS를 이용해 확인하고, 이동할 수 있을 경우에 Queue에 넣어 다시 탐색하는 과정으로 쉽게 풀린다. 하지만 boolean[][] 배열 3개를 이용해 속도를 개선시킨 방법을 설명해보려고 한다.

 

먼저 N과 light에는 입력 값을 넣어주었고, 중요한 건 boolean[][] 배열들이다. on 배열은 불이 켜졌는지 확인하고, visited 배열은 이동할 수 있는 공간을 의미하고, 마지막으로 stop 배열은 이동할 수 있던 공간이지만 불이 켜지지 않았던 공간을 의미한다.

static int N;
static List<int[]>[][] light;
static boolean[][] on;
static boolean[][] visited;
static boolean[][] stop;
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, -1, 0, 1};
static int result;

 

처음 위치인 (1, 1)에 대한 초기화를 해준 후, Queue에 이동할 수 있는 불이 켜진 방을 담는다.

while문을 돌면서 스위치를 통해 불을 킨다. 이전에 불이 켜지지 않았던 위치라면 불을 켜고 result를 카운팅해준다. stop 배열을 통해 이동할 수 있는 위치임을 확인해 true일 경우 큐에 넣어주었다. 이제 상하좌우로 이동하면서 불이 켜진 방이라면 방문 처리를 visit 배열을 통해 해주고, 아니라면 stop 배열을 true로 만들어 이동할 수 있는 공간임을 명시해준다.

public static void solution() {
    // 현재 위치에서 스위치 on
    // 불 켜진 곳에서 bfs를 통해 현재 위치까지 도달할 수 있으면 큐에 넣기

    Queue<int[]> queue = new ArrayDeque<>();

    result = 1;
    on[1][1] = true;
    visited[1][1] = true;
    queue.add(new int[]{1, 1});

    while (!queue.isEmpty()) {
        int[] q = queue.poll();
        int x = q[0];
        int y = q[1];

        // turn on
        for (int[] l : light[x][y]) {
            if (!on[l[0]][l[1]]) {
                on[l[0]][l[1]] = true;
                result++;

                if (stop[l[0]][l[1]]) {
                    queue.add(new int[]{l[0], l[1]});
                }
            }
        }

        for (int d = 0; d < dx.length; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];

            if (nx == 0 || ny == 0 || nx > N || ny > N) continue;
            if (visited[nx][ny]) continue;

            if (on[nx][ny]) {
                visited[nx][ny] = true;
                queue.add(new int[]{nx, ny});
            }
            else {
                stop[nx][ny] = true;
            }
        }
    }
}

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B11967.java

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

class Main {
    static int N;
    static List<int[]>[][] light;
    static boolean[][] on;
    static boolean[][] visited;
    static boolean[][] stop;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int result;

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

    public static void solution() {
        // 현재 위치에서 스위치 on
        // 불 켜진 곳에서 bfs를 통해 현재 위치까지 도달할 수 있으면 큐에 넣기

        Queue<int[]> queue = new ArrayDeque<>();

        result = 1;
        on[1][1] = true;
        visited[1][1] = true;
        queue.add(new int[]{1, 1});

        while (!queue.isEmpty()) {
            int[] q = queue.poll();
            int x = q[0];
            int y = q[1];

            // turn on
            for (int[] l : light[x][y]) {
                if (!on[l[0]][l[1]]) {
                    on[l[0]][l[1]] = true;
                    result++;

                    if (stop[l[0]][l[1]]) {
                        queue.add(new int[]{l[0], l[1]});
                    }
                }
            }

            for (int d = 0; d < dx.length; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];

                if (nx == 0 || ny == 0 || nx > N || ny > N) continue;
                if (visited[nx][ny]) continue;

                if (on[nx][ny]) {
                    visited[nx][ny] = true;
                    queue.add(new int[]{nx, ny});
                }
                else {
                    stop[nx][ny] = true;
                }
            }
        }
    }

    public static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(result+"");

        bw.flush();
        bw.close();
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        light = new List[N+1][N+1];
        on = new boolean[N+1][N+1];
        visited = new boolean[N+1][N+1];
        stop = new boolean[N+1][N+1];

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                light[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());
            light[x][y].add(new int[]{a, b});
        }

        br.close();
    }
}

---

4. 결과 및 회고

다른 분들의 풀이를 보니 문제를 맞았다고 넘어가는게 아니라 알고리즘을 개선할 방법들도 많이 고민해 봐야겠다.

그래도 오늘은 실수 없이 한 번에 풀려고 노력해서 잘 풀린 것 같다.