불켜기_11967.md

🔥 [11967] 불켜기

난이도: 골드 2
소요 시간: 23분
메모리: 23748KB
시간: 224ms

리뷰

• 불을 켜야하는 방이 이미 농부가 접근을 시도했던 방인지 구분해주는 것을 제외하면, 나머지는 bfs로 풀리는 문제였다.

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main_11967_불켜기 {
    static int N;
    static List<int[]>[][] map_switch;

    public static void main(String[] args) throws Exception {
        init();
        System.out.println(bfs());
    }

    static void init() throws Exception {
        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());

        map_switch = new ArrayList[N][N];
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;

            if (map_switch[x][y] == null) {
                map_switch[x][y] = new ArrayList<>();
            }
            map_switch[x][y].add(new int[]{Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()) - 1});
        }
    }

    static int bfs() {
        int[] di = {0, -1, 0, 1};
        int[] dj = {-1, 0, 1, 0};

        boolean[][] map = new boolean[N][N];
        boolean[][] visited = new boolean[N][N];
        boolean[][] next = new boolean[N][N];

        int answer = 1;
        map[0][0] = true;

        Queue<int[]> queue = new LinkedList<>();
        visited[0][0] = true;
        queue.offer(new int[]{0, 0});

        while (!queue.isEmpty()) {
            int[] node = queue.poll();

            //불켜기
            if (map_switch[node[0]][node[1]] != null) {
                for (int[] ij : map_switch[node[0]][node[1]]) {
                    if (!map[ij[0]][ij[1]]) {
                        answer++;
                        map[ij[0]][ij[1]] = true;
                        if (next[ij[0]][ij[1]]) {
                            visited[ij[0]][ij[1]] = true;
                            queue.offer(new int[]{ij[0], ij[1]});
                        }
                    }
                }
            }

            for (int z = 0; z < 4; z++) {
                int ni = node[0] + di[z];
                int nj = node[1] + dj[z];
                if (check(ni, nj)) {
                    if (!map[ni][nj]) {
                        next[ni][nj] = true;
                    } else if (!visited[ni][nj]) {
                        visited[ni][nj] = true;
                        queue.offer(new int[]{ni, nj});
                    }
                }
            }
        }
        return answer;
    }

    static boolean check(int i, int j) {
        if (i < 0 || i >= N || j < 0 || j >= N) return false;
        return true;
    }
}