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

목차

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

---

1. 문제

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

16933번: 벽 부수고 이동하기 3

---

2. 내가 푼 방법

처음에는 이동했던 경로를 확인하기 위해 4차원 배열을 사용해서 풀었지만 공간 복잡도와 시간 복잡도가 다른 분들에 비해 훨 성능이 떨어졌다. 그래서 다른 분들의 코드를 참고하여 다시 푼 문제이다.

 

이동했던 경로를 확인하기 위해 2차원 배열인 Integer[][] visit = new Integer[N][M]; 를 선언해 주었다. visit 배열은 해당 위치까지 이동하면서 최소로 벽은 부순 횟수를 담아둔다.

 

왜 이동 횟수가 아닌 벽을 부순 횟수를 저장할까? 벽을 부순 횟수가 커질수록 이동 횟수도 같이 커지기 때문이다. 그럼 그 반대, 이동 횟수가 커지면 벽을 부순 횟수도 커지는 것도 성립할까? 아니다. 이동할 때 무조건 벽을 부수는 게 아니기 때문에, 우리는 visit 배열에 이동 횟수를 저장해 이용할 수 있는 것이다.

 

아래 코드를 보면 visit[다음위치x][다음위치y] 보다 brokenCnt가 더 작은 경우에만, 큐에 넣는 이동할 경로를 넣는 것을 볼 수 있다. Integer 형으로 선언해 주었으니 null 확인은 필수이다.

현재 위치에서 머물러야 할 때 주의할 점이 있다. 다음 위치가 벽이어서 이동할 수 없을 때(= 머물러야 할 때),  큐에는 moveCnt와 brokenCnt가 함께 오름차순으로 저장되어야 해서  moveCnt+2, brokenCnt+1로 건너뛰면 안된다.

while (!queue.isEmpty()) {
    Tuple t = queue.poll();
    int x = t.x;
    int y = t.y;
    int moveCnt = t.moveCnt; // 홀:낮, 짝:밤
    int brokenCnt = t.brokenCnt;

    if (x == N-1 && y == M-1) {
        result = moveCnt;
        break;
    }

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

        if (nx < 0 || ny < 0 || nx == N || ny == M) continue;

        if (arr[nx][ny] == '1') {
            if (brokenCnt == K) continue;

            if (moveCnt % 2 == 0) { // 현재는 밤, 이동 불가능
                queue.add(new Tuple(x, y, moveCnt + 1, brokenCnt));
            }
            else { // 현재는 낮, 이동 가능
                if (visit[nx][ny] != null && visit[nx][ny] <= brokenCnt + 1) continue;

                visit[nx][ny] = brokenCnt + 1;
                queue.add(new Tuple(nx, ny, moveCnt + 1, brokenCnt+1));
            }
        }
        else {
            if (visit[nx][ny] != null && visit[nx][ny] <= brokenCnt) continue;

            visit[nx][ny] = brokenCnt;
            queue.add(new Tuple(nx, ny,moveCnt + 1, brokenCnt));
        }
    }
}

---

3. 자바 코드

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

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

class Main {
    static int N, M, K;
    static char[][] arr;
    static int result;

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

    public static void solution() {
        Queue<Tuple> queue = new LinkedList<>();
        Integer[][] visit = new Integer[N][M];
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};

        queue.add(new Tuple(0, 0, 1, 0));

        while (!queue.isEmpty()) {
            Tuple t = queue.poll();
            int x = t.x;
            int y = t.y;
            int moveCnt = t.moveCnt; // 홀:낮, 짝:밤
            int brokenCnt = t.brokenCnt;

            if (x == N-1 && y == M-1) {
                result = moveCnt;
                break;
            }

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

                if (nx < 0 || ny < 0 || nx == N || ny == M) continue;

                if (arr[nx][ny] == '1') {
                    if (brokenCnt == K) continue;

                    if (moveCnt % 2 == 0) { // 현재는 밤, 이동 불가능
                        queue.add(new Tuple(x, y, moveCnt + 1, brokenCnt));
                    }
                    else { // 현재는 낮, 이동 가능
                        if (visit[nx][ny] != null && visit[nx][ny] <= brokenCnt + 1) continue;

                        visit[nx][ny] = brokenCnt + 1;
                        queue.add(new Tuple(nx, ny, moveCnt + 1, brokenCnt+1));
                    }
                }
                else {
                    if (visit[nx][ny] != null && visit[nx][ny] <= brokenCnt) continue;

                    visit[nx][ny] = brokenCnt;
                    queue.add(new Tuple(nx, ny,moveCnt + 1, brokenCnt));
                }
            }
        }
    }

    public static class Tuple {
        int x;
        int y;
        int moveCnt;
        int brokenCnt;

        public Tuple(int x, int y, int moveCnt, int brokenCnt) {
            this.x = x;
            this.y = y;
            this.moveCnt = moveCnt;
            this.brokenCnt = brokenCnt;
        }
    }

    public static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(result+"");

        bw.flush();
        bw.close();
    }

    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());
        K = Integer.parseInt(st.nextToken());
        arr = new char[N][M];
        result = -1;

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

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

        br.close();
    }
}

---

4. 결과 및 회고

풀었다고 바로 넘어가지 말고, 이번 문제처럼 다른 분들의 코드도 볼 필요가 있는 것 같다. 시간 단축 아주 보기 조하.