BOJ 11967: 불 켜기

문제 풀이

이동 가능한 곳의 스위치를 전체 켠다.
스위치를 켜기 전에 willLight라는 Queue를 만들어 저장해둔다.
해당 위치에서 이동 가능한 경우를 모두 체크한 뒤에 willLight를 돌면서 불을 켜고 켜진 위치에서 4방향으로 방문했던 적이 있는 지점을 확인한다.
방문했던 적이 있는 지점과 맞닿아 있다면 불이 켜진 위치도 이동 가능한 지점이므로 q에 추가해준다.
이렇게 한 이유는 visit으로 방문 경로를 체크하는데 불이 이미 방문한 경로 주변으로 켜지면 다시 돌아갈 방법이 없기 때문이다.
하지만 최근에 켜진 불이 방문 경로와 맞닿아 있다면 언제든지 그 곳을 방문할 수 있다는 의미이므로 앞으로 체크해야하는 경로에 추가해준다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static class LightIndex {
        int i;
        int j;

        LightIndex(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
    static int N;
    static ArrayList<LightIndex>[][] room;
    static boolean[][] light;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        light = new boolean[N][N];
        light[0][0] = true;

        room = new ArrayList[N][N];
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                room[i][j] = new ArrayList<>();
            }
        }
        int M = Integer.parseInt(st.nextToken());

        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int startI = Integer.parseInt(st.nextToken()) - 1;
            int startJ = Integer.parseInt(st.nextToken()) - 1;
            int endI = Integer.parseInt(st.nextToken()) - 1;
            int endJ = Integer.parseInt(st.nextToken()) - 1;

            room[startI][startJ].add(new LightIndex(endI, endJ));
        }

        check();
        System.out.print(count());
    }
    static int[] dirI = {0, 0, 1, -1};
    static int[] dirJ = {1, -1, 0, 0};
    public static void check() {
        Queue<LightIndex> q = new LinkedList<>();
        q.add(new LightIndex(0, 0));
        boolean[][] visit = new boolean[N][N];
        visit[0][0] = true;
        while(!q.isEmpty()) {
            LightIndex temp = q.poll();
            Queue<LightIndex> willLight = new LinkedList<>();
            if(!room[temp.i][temp.j].isEmpty()) {
                for(LightIndex t : room[temp.i][temp.j]) {
                    if(light[t.i][t.j]) {
                        continue;
                    }
                    willLight.add(t);
                }
            }

            for(int index = 0; index < 4; index++) {
                int nextI = temp.i + dirI[index];
                int nextJ = temp.j + dirJ[index];

                if(nextI < 0 || nextI >= N || nextJ < 0 || nextJ >= N || visit[nextI][nextJ]) {
                    continue;
                }
                if(light[nextI][nextJ]) {
                    q.add(new LightIndex(nextI, nextJ));
                    visit[nextI][nextJ] = true;
                }
            }
            while(!willLight.isEmpty()) {
                LightIndex l = willLight.poll();
                light[l.i][l.j] = true;
                if(l.i + 1 < N && visit[l.i + 1][l.j]) {
                    q.add(l);
                    visit[l.i][l.j] = true;
                    continue;
                }
                if(l.i - 1 >= 0 && visit[l.i - 1][l.j]) {
                    q.add(l);
                    visit[l.i][l.j] = true;
                    continue;
                }
                if(l.j + 1 < N && visit[l.i][l.j + 1]) {
                    q.add(l);
                    visit[l.i][l.j] = true;
                    continue;
                }
                if(l.j - 1 >= 0 && visit[l.i][l.j - 1]) {
                    q.add(l);
                    visit[l.i][l.j] = true;
                    continue;
                }
            }
        }
    }
    public static int count() {
        int answer = 0;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(light[i][j]) {
                    answer++;
                }
            }
        }
        return answer;
    }
}

백준
github