[백준 11967] 불켜기 (JAVA)

백준(BOJ) 11967 불켜기

 

난이도
230527 기준 골드 2

사용 알고리즘
BFS

문제 링크
https://www.acmicpc.net/problem/11967

11967번: 불켜기

 

 

풀이 과정

 

1. 문제 읽기(중요한 부분 굵은 표시)

 

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

 

 

출력

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

 

 

2. 어떤 알고리즘을 사용할 것인가

 

 N이 2~100이니 무난하게 BFS로 풀면 될 것 같습니다.

 

 

3. 풀이 구상

 

 방에 스위치가 담겨있는 정보를 일단 어딘가에 저장을 합니다. x,y방에서 a,b방의 불을 켜고 끌 수 있다는 것은 List의 2차원 배열을 만들어서 [x][y]의 리스트에 a,b의 정보를 넣어주는 방식으로 저장할 수 있습니다.

 이제 1,1부터 bfs를 돌리면 되는데 주의할 점은 처음에는 불이 안켜져있어서 못가는 방이 나중에 다른 곳에서 불이 켜지고 갈 수 있게 되었지만 연결 된 방이 이미 visited 처리 되어서 불이 켜져있지만 못가는 경우가 생길 수 있습니다. 저는 불이 켜지거나 안켜지거나 일단 도달이 가능한지 여부를 저장해주는 reachable이라는 boolean 2차원 배열을 만들어서 나중에 불이 켜졌을 때 visited가 false고 reachable이 true인 경우에는 bfs 큐에 넣어주는 방식으로 처리 해줬습니다.

 

4. 코드 작성

 

1. 정답 코드

import java.io.*;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int N, M;

    static List<RC>[][] ls;

    static boolean[][] ableMatrix;
    static boolean[][] visitedMatrix;
    static boolean[][] reachableMatrix;

    static int result;

    static class RC {
        int r;
        int c;

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

    public static void main(String[] args) throws IOException {


        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        ls = new List[N + 1][N + 1];
        ableMatrix = new boolean[N + 1][N + 1];
        visitedMatrix = new boolean[N + 1][N + 1];
        reachableMatrix = new boolean[N + 1][N + 1];

        for (int r = 1; r <= N; r++) {
            for (int c = 1; c <= N; c++) {
                ls[r][c] = new LinkedList<RC>();
            }
        }

        for (int i = 1; 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());

            //
            ls[x][y].add(new RC(a, b));
        }
        ableMatrix[1][1] = true;

        bfs();
        result = 0;
        for (int r = 1; r <= N; r++) {
            for (int c = 1; c <= N; c++) {
                if (ableMatrix[r][c] == true) {
                    result++;
                }
            }
        }

        bw.write(result + "");
        bw.flush();
        bw.close();
        br.close();
    }

    // 상 하 좌 우
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};

    private static void bfs() {
        Queue<RC> q = new LinkedList<>();
        q.offer(new RC(1, 1));

        while (q.size() > 0) {
            RC poll = q.poll();
            int r = poll.r;
            int c = poll.c;
            // 일단 방문 했던 곳이면 다시 올 필요가 없으니 컨티뉴
            if (visitedMatrix[r][c] == true) {
                continue;
            }
            // 첫 방문이면 visitedMatrix[r][c] 넣어주고
            visitedMatrix[r][c] = true;


            // 지금 방문한 곳에서 스위치 켜주기
            for (RC rc : ls[r][c]) {
                // 스위치 켠 곳은 ableMatirx가 true로
                ableMatrix[rc.r][rc.c] = true;
                // 방문은 안했고
                if (visitedMatrix[rc.r][rc.c] == false) {
                    // 갈 수는 있는 곳이면
                    if (reachableMatrix[rc.r][rc.c] == true) {
                        // 바로 q에 넣어주기
                        q.offer(new RC(rc.r, rc.c));
                    }
                }
            }

            // 방문한 곳에서 4방 탐색
            for (int d = 0; d < 4; d++) {
                int nr = r + dr[d];
                int nc = c + dc[d];

                if (nr >= 1 && nr <= N && nc >= 1 && nc <= N) {
                    // 방문한 곳에서 4방 탐색해서 갈 수 있으면 reachableMatrix true
                    reachableMatrix[nr][nc] = true;
                    // 불이 켜져있고
                    if (ableMatrix[nr][nc] == true) {
                        // 방문 안했으면
                        if (visitedMatrix[nr][nc] == false) {
                            // q에 넣어주기
                            // 이걸 함으로써 첫 사방탐색 때는 불이 안켜져서 못갔는데
                            // 나중에 불을 켜서 갈 수 있는 곳이 생기면 챙겨 줄 수 있음
                            q.offer(new RC(nr, nc));
                        }
                    }
                }
            }
        }
    }
}

 

 

2. 오답노트

 

 출력 조건을 보시면 베시가 방문한 방의 최대 개수가 아니라 불을 켤 수 있는 방의 최대 개수를 출력 하라고 되어 있습니다. 저는 처음에 bfs니까 당연히 방문한 방 체크하면 되지 하고 풀어서 한 번 틀렸습니다. bfs를 다 돌리고 불이 켜져있는 것을 체크하는 이차원 배열에서 불 켜진 방을 세는 것으로 바꾸니 통과됐습니다.

 

---

풀이 후기

 실제 코딩테스트에서는 틀렸는지 바로 나오지가 않으니 문제 조건을 잘 읽고 풀어야 합니다. 안그러면 분명 풀었다 생각했는데 틀리는 경우가 생깁니다.

 정말 오랜만에 알고리즘 풀이 글을 올리는데요 그동안 싸피 합격 후기가 구글 검색 엔진의 픽을 받아 조회수가 꽤나 많이 나왔더라고요 알고리즘 풀이를 마지막으로 올린 날 부터 지금까지 싸피 2학기를 보내며 프로젝트를 3개 진행했습니다. 바쁘다는 핑계로 글은 안올렸지만 알고리즘은 그동안 꾸준히 풀긴했답니다. 이제 싸피도 끝이 보이고 여유가 생겼으니 블로그에 글을 다시 꾸준히 올려보겠습니다.