[백준] 11967번 - 불켜기(java)

Baekjoon 11967 - 불켜기 (클릭 시 이동)

문제

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

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

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	5015	1342	914	26.524%

입력

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

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

출력

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

풀이 (BFS)

용어 : graph[][] - 연결리스트의 2차원 배열(입력값), isShine[][] - 불이 켜진 방 , visited[][] - 스위치를 켠 방, isPassable[][] - 이동할 수 있는 방(불켜진 방과 붙어있는 방 = true)

1. queue에서 꺼낸 위치에 방문하여 불을 켤 수 있는 방들(입력값)의 불을 켜고 켠 갯수를 정답에 반영한다(Ans++).
2. 불을 새로 켠 방이 아직 방문하지 않았고(스위치를 켜지 않았고 => !visited) 이동할 수 있는 방(isPassable)이라면 queue에 넣으면서 visited를 true로 만든다.(queue에 들어가면 스위치를 작동시킬 것이기 때문)
3. 현재 위치([1]의 queue에서 꺼낸 값)의 사방을 이동할 수 있는 방(isPassable= true)으로 만든다.
4. 만약 불이 켜져있는 방이라면 queue에 넣고 visited를 true로 만든다.(이동할 수 있으므로 스위치를 작동시킬 것)

최종 소스코드

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

public class BJ_G3_11967_불켜기{
    static int N, M;
    static int Ans;
    static int[][] deltas = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    static boolean[][] isShine;     // 불이 켜져있는 방들
    static boolean[][] visited;     // 불을 켠(스위치를 작동한) 방들
    static boolean[][] isPassable;  // 이동할 수 있는 곳(불켠 방의 주변 방들)
    static Position[][] graph;

    static class Position {
        int r, c;
        Position link;

        public Position(int r, int c) {
            this.r = r;
            this.c = c;
        }

        public Position(int r, int c, Position link) {
            this.r = r;
            this.c = c;
            this.link = link;
        }
    }

    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());
        M = Integer.parseInt(st.nextToken());

        isShine = new boolean[N + 1][N + 1];
        visited = new boolean[N + 1][N + 1];
        isPassable = new boolean[N + 1][N + 1];
        graph = new Position[N + 1][N + 1];

        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());
            graph[x][y] = new Position(a, b, graph[x][y]);
        }        // 입력 끝
        isShine[1][1] = true;
        visited[1][1] = true;
        Ans++;    // (1,1)은 항상 불이 켜져있다.

        bfs();

        System.out.println(Ans);
    }

    static void bfs() {
        Queue<Position> queue = new LinkedList<>();

        queue.offer(new Position(1, 1));
        isPassable[1][1] = true;

        while (!queue.isEmpty()) {
            Position cur = queue.poll();
            // 불을 켤 수 있는 곳을 모두 켠다.
            for (Position temp = graph[cur.r][cur.c]; temp != null; temp = temp.link) {
                if (!isShine[temp.r][temp.c]) {    // 불이 꺼져있었다면 불을 켜고 갯수를 추가한다.
                    isShine[temp.r][temp.c] = true;
                    Ans++;
                }
                if (isPassable[temp.r][temp.c] && !visited[temp.r][temp.c]) {    // 이동할 수 있는 위치이며, 스위치를 작동시키지 않았다면 queue에 넣는다.
                    queue.offer(new Position(temp.r, temp.c));
                    visited[temp.r][temp.c] = true;
                }

            }

            for (int i = 0; i < 4; i++) {    // 새로 방문한 방의 사방을 확인한다.
                int nr = cur.r + deltas[i][0];
                int nc = cur.c + deltas[i][1];

                if (isIn(nr, nc)) {
                    isPassable[nr][nc] = true;    // 이 때 접근한 모든 방을 이동할 수 있는 방으로 만든다.
                    if (!visited[nr][nc] && isShine[nr][nc]) {    // 불이 켜진 방을 만나면 queue에 넣는다. 이 때 들린 방 중 불 켜진 방이 있다면 queue에 넣는다.
                        queue.offer(new Position(nr, nc));
                        visited[nr][nc] = true;
                    }
                }
            }
        }
    }

    static boolean isIn(int r, int c) {
        return r > 0 && r <= N && c > 0 && c <= N;
    }

}