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

목차

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

---

1. 문제

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

14442번: 벽 부수고 이동하기 2

---

2. 내가 푼 방법

벽 부수고 이동하기 1을 풀었다면, 이번 문제도 BFS 알고리즘을 사용해 쉽게 풀 수 있을 것이다.

 

벽을 K번까지 부술 수 있는 것이며, 이를 위해 벽은 K번 부쉈을 때 이동했던 경로인지 확인하는 작업이 필요하다. 또한, 이동한 횟수가 작을 경우 더 높은 우선순위를 갖는 PriorityQueue를 이용하여 (N-1, M-1)에 도달했을 때 바로 break; 문으로 빠져나올 수 있도록 했다.

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B14442.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<>();
        boolean[][][] visit = new boolean[K+1][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 move = t.move;
            int broken = t.broken;

            if (x < 0 || y < 0 || x >= N || y >= M) continue;
            if (broken > K || visit[broken][x][y]) continue;
            if (x == N-1 && y == M-1) {
                result = move;
                break;
            }

            visit[broken][x][y] = true;

            int cnt = (arr[x][y] == '1') ? 1 : 0;
            for (int i = 0; i < dx.length; i++) {
                queue.add(new Tuple(x+dx[i], y+dy[i], move+1, broken+cnt));
            }
        }
    }

    public static class Tuple implements Comparable<Tuple> {
        int x;
        int y;
        int move;
        int broken;

        public Tuple (int x, int y, int move, int broken) {
            this.x = x;
            this.y = y;
            this.move = move;
            this.broken = broken;
        }

        @Override
        public int compareTo(Tuple t) {
            return this.move - t.move;
        }
    }

    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. 결과 및 회고

이번 문제는 쏘이지,,,