[JAVA] BOJ 백준 16946번 - 벽 부수고 이동하기 4

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

16946번: 벽 부수고 이동하기 4

---

2. 내가 푼 방법

자칫하면 바로 시간초과가 발생할 수 있는 문제이다.

 

나는 처음에 큐 한 개와 for문을 돌려 풀었는데, 다른 사람과 비교했을 때 속도 차이가 많이 나서 Deque 큐 두 개를 이용해 다시 풀었다. Deque는 큐나 스택처럼 사용할 수 있는데 스택과 비교했을 때는 상황에 따라 다르지만 양 끝쪽에서 행해지는 연산이 O(1) 시간복잡도를 가지기 때문에 LinkedList보다 빠르다는 강점을 가진다. 하지만 멀티 스레드 환경에서 필요한 동기화를 제공하지 않기 때문에, 실제 코드에서 사용할 땐 주의하도록 하자.

 

먼저 입력을 받을 때 벽인 부분은 이동할 수 있는 칸의 수를 저장해 두는 cnt 배열을 1로 초기화해주었다.

for (int i = 0; i < N; i++) {
    String line = br.readLine();

    for (int j = 0; j < M; j++) {
        if (line.charAt(j) == '1') {
            arr[i][j] = 1;
            cnt[i][j] = 1;
        }
        else {
            arr[i][j] = 0;
        }
    }
}

 

그 후, 벽이 아닌 부분을 2 이상으로 arr 값을 변경해 주는데, queue와 첫 번째 while문의 경우에는 벽이 아닌 부분끼리 연결시켜 같은 번호로 설정될 수 있도록 했고, countingQueue와 두 번째 while문의 경우에는 앞서 첫 번째 while문에서 마주한 벽인 부분을 큐에 넣어준 것이다.

따라서 해당 위치에 있는 cnt 값을 첫 번째 while문에서 카운팅 한 벽이 아닌 부분들의 개수를 더해주면 된다.

public static void solution() {
    islandCnt = 2;

    // 1은 벽, 2 이상은 이동 가능한 동일 island
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (arr[i][j] == 0 && !visit[i][j]) {
                bfs(i, j);
                islandCnt++;
            }
        }
    }
}

public static void bfs(int i, int j) {
    Queue<int[]> queue = new ArrayDeque<>();
    Queue<int[]> countingQueue = new ArrayDeque<>();
    int islandArrCnt = 0;

    queue.add(new int[]{i, j});
    arr[i][j] = islandCnt;

    while (!queue.isEmpty()) {
        int[] t = queue.poll();
        int x = t[0];
        int y = t[1];

        islandArrCnt++;

        for (int d = 0; d < dx.length; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];

            if (nx < 0 || ny < 0 || nx >= N || ny >= M || visit[nx][ny]) continue;

            visit[nx][ny] = true;

            if (arr[nx][ny] != 0) {
                if (arr[nx][ny] == 1) {
                    countingQueue.add(new int[]{nx, ny});
                }
                continue;
            }

            arr[nx][ny] = islandCnt;
            queue.add(new int[]{nx, ny});
        }
    }

    while (!countingQueue.isEmpty()) {
        int[] t = countingQueue.poll();
        cnt[t[0]][t[1]] += islandArrCnt;
        cnt[t[0]][t[1]] %= 10;
        visit[t[0]][t[1]] = false;
    }
}

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B16946.java

import java.util.*;
import java.io.*;

class Main {
    static int N, M;
    static int[][] arr, cnt;
    static boolean[][] visit;
    static int islandCnt;

    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};

    public static void main (String[] args) throws IOException {
        input();
        solution();
        output();
    }

    public static void solution() {
        islandCnt = 2;

        // 1은 벽, 2 이상은 이동 가능한 동일 island
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (arr[i][j] == 0 && !visit[i][j]) {
                    bfs(i, j);
                    islandCnt++;
                }
            }
        }
    }

    public static void bfs(int i, int j) {
        Queue<int[]> queue = new ArrayDeque<>();
        Queue<int[]> countingQueue = new ArrayDeque<>();
        int islandArrCnt = 0;

        queue.add(new int[]{i, j});
        arr[i][j] = islandCnt;

        while (!queue.isEmpty()) {
            int[] t = queue.poll();
            int x = t[0];
            int y = t[1];

            islandArrCnt++;

            for (int d = 0; d < dx.length; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];

                if (nx < 0 || ny < 0 || nx >= N || ny >= M || visit[nx][ny]) continue;

                visit[nx][ny] = true;

                if (arr[nx][ny] != 0) {
                    if (arr[nx][ny] == 1) {
                        countingQueue.add(new int[]{nx, ny});
                    }
                    continue;
                }

                arr[nx][ny] = islandCnt;
                queue.add(new int[]{nx, ny});
            }
        }

        while (!countingQueue.isEmpty()) {
            int[] t = countingQueue.poll();
            cnt[t[0]][t[1]] += islandArrCnt;
            cnt[t[0]][t[1]] %= 10;
            visit[t[0]][t[1]] = false;
        }
    }

    public static void output() throws IOException {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (arr[i][j] == 1) {
                    sb.append(cnt[i][j] % 10);
                }
                else {
                    sb.append(cnt[i][j]);
                }
            }
            sb.append("\n");
        }

        System.out.print(sb.toString());
    }

    public static void input() 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());
        arr = new int[N][M];
        cnt = new int[N][M];
        visit = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            String line = br.readLine();

            for (int j = 0; j < M; j++) {
                if (line.charAt(j) == '1') {
                    arr[i][j] = 1;
                    cnt[i][j] = 1;
                }
                else {
                    arr[i][j] = 0;
                }
            }
        }

        br.close();
    }
}

---

4. 결과 및 회고

문제를 풀 때 중간 값을 알 필요가 없을 때 LinkedList보다는 Deque를 사용해야겠다. 그리고 다시 풀었을 때 시간이 꽤 많이 단축돼서 보기 좋은 것 같다ㅎㅎ