백준 11967번 <불켜기>

백준 알고리즘 11967번

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

11967번: 불켜기

---

11967번

농부 존은 최근에 N × N개의 방이 있는 거대한 헛간을 새로 지었다.

각 방은 (1, 1)부터 (N,N)까지 번호가 매겨져있다(2 ≤ N ≤ 100). 

베시는 유일하게 불이 켜져있는 방인 (1, 1)방에서 출발한다. 

베시는 불이 켜져있는 방으로만 들어갈 수 있고, 각 방에서는 상하좌우에 인접한 방으로 움직일 수 있다.

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

 

입력으로 방의 크기 N이 들어오고 스위치 정보의 개수 M이 들어온다.

그 다음 M개의 줄에 걸쳐 스위치의 정보가 들어오는데 x y a b가 들어올 때 (x, y) 방에서 (a, b) 방의 불을 켤 스위치가 있다는 의미 이다.

 

출력으로 베시가 불을 켤 수 있는 방의 최대 개수를 구해 출력하면 된다.

---

문제 해결

어려웠다. 처음에 문제를 잘못 이해해서 스위치의 정보가 간선의 정보인줄 알고 삽질을 했다.

 

베시가 움직일 수 있는 것은 불이 켜진 인접한 방이어야 하기 때문에 불이 켜져있는지와 방문했는지를 확인하는 배열이 2개가 있어야 한다. 그래서 불이 켜져있는지를 의미하는 turn 배열과 방문 체크를 하는 visit 배열을 사용하였다.

 

또한 스위치의 정보를 ArrayList의 ArrayList의 ArrayList로 저장했다.

ArrayList.get(i).get(j) 는 (i, j) 방에 있는 스위치의 정보의 list를 의미한다.

 

풀면서 이전 방에서 인접한 방이 불이 나중에 켜져도 갈 수 있는게 어려웠다.

주어진 입력으로 예를 들어보면 아래와 같은 과정으로 불이 켜진다.

1. 불이 켜져 있는 (1, 1) 방을 방문한다.
2. (1, 1)에서 (1, 2), (1, 3) 방의 불을 켤 수 있다.
3. (1, 1)의 인접한 방이고 불이 켜져있는 (1, 2)를 방문한다.
4. (1, 2)에는 스위치가 없다.
5. (1, 2)의 인접한 방이고 불이 켜져있는 (1, 3)를 방문한다.
6. (1, 3)에서 (2, 1) 방의 불을 켤 수 있다.
7. (1, 1)의 인접한 방이고 불이 켜져있는 (2, 1)를 방문한다.
8. (2, 1)에서 (2, 2) 방의 불을 켤 수 있다.
9. (2, 1)의 인접한 방이고 불이 켜져있는 (2, 2)를 방문한다.
10. (2, 2)에는 스위치가 없다.
11. (2, 2)에서 방문할 수 있는 방이 없다.

위에서 7번 부분을 어떻게 구현할지 고민이 많이 됐다.

현재 방의 인접한 방을 모두 큐에 넣고 불이 켜지지 않은 방은 다시 큐에 넣는 것으로 해결할 수 있을까 했는데 그러면 큐가 비지 않기 때문에 무한 루프에 빠지게 되었다.

 

고민을 하다가 다른 종료 조건을 찾았는데 큐의 크기만큼 한 사이클을 돌면서 방문한 방이 하나도 없는 경우에는 while문을 빠져나오게 했다. 방문한 방이 하나도 없다는 것은 큐에 새로운 방이 들어가지 않았다는 의미이기 때문에 결국 똑같은 방들을 확인하고 방문하지 못하기 때문에 큐에 다시 넣는 과정이 계속 반복된다는 의미이기 때문이다.

 

구체적인 로직은 다음과 같다.

• 불이 켜져있는 (1, 1) 방을 먼저 큐에 넣는다. 방문체크를 한다.
• 큐가 빌 때까지 while문을 돈다.
  • 큐의 현재 크기를 size에 저장하고 방문한 방의 개수를 count할 temp 변수를 0으로 초기화한다.
  • size 만큼 for문을 돈다.
    • 현재 방이 불이 켜져있지 않다면 다시 큐에 넣는다.
    • 그렇지 않다면
      • 방문할 수 있기 때문에 temp 값을 1 증가시킨다.
      • 현재 방에 있는 스위치로 불을 켠다.
      • 현재 방의 인접한 방 중에 방문하지 않은 방을 큐에 넣는다.
  • 만약 temp 값이 0이라면 방문한 방이 없다는 의미이고 이는 종료 조건을 의미하기 때문에 while문을 빠져나간다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;

public class BOJ_11967 {
    static class Point{
        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static int N, M;
    static int[] di = {-1, 1, 0, 0};
    static int[] dj = {0, 0, -1, 1};
    static boolean[][] turn, visit;
    static ArrayList<ArrayList<ArrayList<Point>>> adj;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inArr = br.readLine().split(" ");
        N = Integer.parseInt(inArr[0]);
        M = Integer.parseInt(inArr[1]);
        adj = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            adj.add(new ArrayList<>());
            for (int j = 0; j <= N; j++) {
                adj.get(i).add(new ArrayList<>());
            }
        }

        for (int i = 0; i < M; i++) {
            inArr = br.readLine().split(" ");
            int x = Integer.parseInt(inArr[0]);
            int y = Integer.parseInt(inArr[1]);
            int a = Integer.parseInt(inArr[2]);
            int b = Integer.parseInt(inArr[3]);
            // (x, y)에서  (a, b) 방의 불을 켤 수 있다.
            adj.get(x).get(y).add(new Point(a, b));
        } // end input
        BFS();
        System.out.println(count());
    }
    static void BFS(){
        Queue<Point> Q = new ArrayDeque<>();
        visit = new boolean[N + 1][N + 1];
        turn = new boolean[N + 1][N + 1];
        visit[1][1] = true;
        turn[1][1] = true;
        Q.add(new Point(1, 1));
        while (!Q.isEmpty()) {
            int temp = 0;       // temp : 들어갈 수 있는 방의 개수
            int size = Q.size();
            for (int s = 0; s < size; s++) {
                Point pnt = Q.poll();
                if (!turn[pnt.x][pnt.y]) {  // 불이 안켜져있으면
                    Q.add(pnt);             // 다시 큐에 넣는다.
                    continue;
                }
                temp++;     // 불이 켜져있으니까 들어갈 수 있는 방
                // 현재 방에서 켤 수 있는 방의 불 켜기
                ArrayList<Point> tp = adj.get(pnt.x).get(pnt.y);
                for (int i = 0; i < tp.size(); i++) {
                    turn[tp.get(i).x][tp.get(i).y] = true;
                }
                // 현재 방에서 인접한 방을 방문하기
                for (int k = 0; k < 4; k++) {
                    int nx = pnt.x + di[k];
                    int ny = pnt.y + dj[k];
                    if (nx < 1 || ny < 1 || nx > N || ny > N || visit[nx][ny]) {
                        continue;
                    }
                    visit[nx][ny] = true;
                    Q.add(new Point(nx, ny));
                }
            }
            if (temp == 0) break;
        }
    }

    static int count() {
        int cnt = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (turn[i][j]) cnt++;
            }
        }
        return cnt;
    }
}

---

결과

 

---

5 13
1 1 1 2
1 1 1 3
1 1 2 1
1 2 2 1
1 2 2 3
1 2 3 1
1 2 1 3
1 2 5 1
1 2 5 3
1 3 2 4
1 3 4 1
1 3 4 3
1 3 3 4

12