[BFS/자바] k개의 벽 없애기

유형 파악

이 문제는 2차원 배열 상의 출발지에서 목적지까지 이동시간의 최소를 구하는 문제이면서, 이동간 시간 가중치가 동일하기 때문에 전형적인 BFS 문제라고 이해할 수 있다.

아울러, 몇 개의 점을 선택하여 제거하는 경우를 세야 하므로 이 부분은 백트래킹 로직을 활용하여 풀어내 주었다.

 

제출 코드

구성했던 로직의 특징은, 여러 경우에서 도착지에 도달하는 시간이 도출될텐데, 그 경우 중 가장 빠른 경우에서의 시간을 구하는 것을 우선순위 큐를 활용하여 도출해줬다는 것과, 제거하려는 벽을 중복으로 선택하지 않기 위해 selected[][] 라는 배열을 운영한 것이다.

 

개인적으로 헤맨 부분은, 백트래킹을 통해 제거할 벽을 모두 선택했을 때 bfs를 수행하기 위해 관련 변수들을 초기화해줘야 한다는 것이다. 이를 다른 부분에서 초기화하려고 했기에 원하는 시점에 초기화가 일어나지 않아서 원하는 답을 얻을 수 없었다. 이 부분은 나만 헷갈릴 부분인 것 같고, 대부분은 이런 실수는 하지 않을 것 같다.

package 코드트리.그래프.BFS;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class k개의_벽_없애기 {
    private static Queue<Pair> q = new LinkedList<>();
    private static int[][] arr;
    private static int[][] ans;
    private static boolean[][] visited;
    private static boolean[][] selected;

    private static int r1,c1,r2,c2;

    private static List<Pair> li = new ArrayList<>();

    private static Queue<Integer> pq = new PriorityQueue<>(); // 최단거리 산출
    private static int n, k;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());


        /*
        * 입력받을 때, 1인 좌표를 li에 저장해두고
        * 나중에 s
        * */

        arr = new int[n][n];
        ans = new int[n][n];
        selected = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                int num = Integer.parseInt(st.nextToken());
                if (num == 1) {
                    li.add(new Pair(i, j));
                }
                arr[i][j] = num;
            }
        }
        st = new StringTokenizer(br.readLine());
        r1 = Integer.parseInt(st.nextToken()) - 1;
        c1 = Integer.parseInt(st.nextToken()) - 1;
        st = new StringTokenizer(br.readLine());
        r2 = Integer.parseInt(st.nextToken()) - 1;
        c2 = Integer.parseInt(st.nextToken()) - 1;



        go(0);

        if (pq.isEmpty()) {
            System.out.println(-1);
        } else {
            System.out.println(pq.poll());
        }

    }
    private static void bfs() {
        int[] dx = new int[]{1, 0, -1, 0};
        int[] dy = new int[]{0, 1, 0, -1};

        while (!q.isEmpty()) {
            Pair p = q.poll();
            int x = p.x;
            int y = p.y;
            for (int i = 0; i < 4; i++) {
                int newY = y + dy[i];
                int newX = x + dx[i];
                if (canGo(newY, newX)) {
                    visited[newY][newX] = true;
                    ans[newY][newX] = ans[y][x] + 1;
                    q.add(new Pair(newY, newX));
                }
            }

        }

    }

    private static void go(int cnt) {
        if (cnt == k) {
            ans = new int[n][n];
            visited = new boolean[n][n];
            q.add(new Pair(r1, c1));
            visited[r1][c1] = true;
            bfs();
            if (ans[r2][c2] > 0) {
                pq.add(ans[r2][c2]);
            }
            return;
        }
        for (Pair pair : li) {
            int x = pair.x;
            int y = pair.y;
            if (!selected[y][x]) {
                arr[y][x] = 0;
                selected[y][x] = true;
                cnt++;

                go(cnt);

                arr[y][x] = 1;
                selected[y][x] = false;
                cnt--;
            }
        }
    }

    private static boolean inRange(int y, int x) {
        return y >= 0 && y < n && x >= 0 && x < n;
    }

    private static boolean canGo(int y, int x) {
        return inRange(y, x) && arr[y][x] == 0 && !visited[y][x];
    }

    private static class Pair {
        private int x, y;

        private Pair(int y, int x) {
            this.x = x;
            this.y = y;
        }
    }
}