[코드트리/INTERMEDIATE LOW] k개의 벽 없애기 (JAVA)

📖 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

 

💡  풀이 방식

• 백트래킹 + BFS

필요 자료구조
- dx/dy 배열
- 2차원 격자 저장용 int형 배열
- 2차원 최단 거리 저장용 int형 배열
- 벽 위치 저장할 리스트
- dfs용 뽑은 벽 인덱스 저장할 리스트
- bfs용 방문 표시 배열
- bfs용 위치 저장할 큐

 

백트래킹으로 없앨 벽 k개를 고른다.

 

벽 k개를 골랐을 때, 해당 인덱스의 벽을 제거하고 > BFS 통해 최소 시간을 구하고 > 없앴던 벽을 원상복구한다. 

BFS는 아래 과정으로 진행한다.

   1) 방문 배열과 최단 거리 배열을 초기화한다.

   2) 시작 위치 (r1,c1) 에서부터 BFS를 진행한다.

   ┕ 격자 범위 내에 있고, 방문한 적 없고, 칸의 값이 0이라면 이동할 수 있다.

  3) 만약 도착 위치 (r2,c2)를 방문한 적 있는 경우에만 최소 시간을 갱신한다.

 

 

💥 유의사항

벽 없애고 bfs 해봤다가 다시 원상복구하는 거 잊지 말기

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
 
    static int n,k;
    static int[][] grid;
    static int[][] pos;    // 시작 위치, 도착 위치 저장용 배열
 
    // findMin용
    static List<int[]> walls = new ArrayList<>();   // 벽 위치 저장용 리스트
    static List<Integer> list = new ArrayList<>();
 
    // bfs용
    static boolean[][] visited;
 
    static int answer = Integer.MAX_VALUE;
 
    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());
 
        grid = new int[n][n];
        for(int i = 0 ; i < n ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < n ; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
 
                if(grid[i][j] == 1) walls.add(new int[] {i, j});
            }
        }
 
        pos = new int[2][2];
        for(int i = 0 ; i < 2 ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int r = Integer.parseInt(st.nextToken()) - 1;
            int c = Integer.parseInt(st.nextToken()) - 1;
 
            pos[i][0] = r;
            pos[i][1] = c;
        }
 
        visited = new boolean[n][n];
        findMin(0, 0);
        System.out.println(answer == Integer.MAX_VALUE ? -1 : answer);
    }
 
    private static void findMin(int idx, int depth) {
        if(depth == k) {
            // 1. 벽 제거하기
            for(int i : list) {
                int[] num = walls.get(i);
                grid[num[0]][num[1]] = 0;
            }
 
            // 2. 최소 시간 구하기
            bfs(pos[0][0], pos[0][1]);
 
            // 3. 벽 원상복구하기
            for(int i : list) {
                int[] num = walls.get(i);
                grid[num[0]][num[1]] = 1;
            }
 
            return;
        }
 
        for(int i = idx ; i < walls.size() ; i++) {
            list.add(i);
            findMin(i + 1, depth + 1);
            list.remove(list.size() - 1);
        }
    }
 
    private static void init() {
        for(int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < n ; j++) {
                visited[i][j] = false;
            }
        }        
    }
 
    private static void bfs(int x, int y) {
        init();
        int[][] dist = new int[n][n];
 
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {x, y});
 
        visited[x][y] = true;
 
        while(!q.isEmpty()) {
            int[] now = q.poll();
 
            for(int dir = 0 ; dir < 4 ; dir++) {
                int nx = now[0] + dx[dir];
                int ny = now[1] + dy[dir];
 
                if(canGo(nx, ny)) {
                    visited[nx][ny] = true;
                    q.add(new int[] {nx, ny});
                    dist[nx][ny] = dist[now[0]][now[1]] + 1;
                }
            }
        }
 
        int endR = pos[1][0];
        int endC = pos[1][1];
        if(visited[endR][endC]) {
            answer = Math.min(answer, dist[endR][endC]);
        }
    }
 
    private static boolean canGo(int x, int y) {
        return (inRange(x, y) && !visited[x][y] && grid[x][y] == 0);
    }
 
    private static boolean inRange(int x, int y) {
        return (0 <= x && x < n && 0 <= y && y < n);
    }
}

 

 

 

➕ 다른 풀이 방식

백트래킹 이렇게 할 수도

public static void findMin(int idx, int cnt) {
    if(idx == (int) walls.size()) {
        if(cnt == k) {
            push(r1, c1, 0);	// 시작점 큐에 넣고 시작
            int minDist = BFS();
            ans = Math.min(minDist, ans);
        }
        return;
    }

    // 해당 인덱스의 벽 사용하는 경우
    grid[walls.get(idx).x][walls.get(idx).y] = 0;
    findMin(idx + 1, cnt + 1);
    grid[walls.get(idx).x][walls.get(idx).y] = 1;

    // 해당 인덱스의 벽 사용하지 않는 경우
    findMin(idx + 1, cnt);
}

 

---

💦 어려웠던 점

45분 소요,,

백트래킹 + BFS 문제 재밌다..!!!!

 

담엔 나도 push 메소드로 큐에 새로운 위치 추가하고, 방문 여부 표시하고, 시작점으로부터 최단 거리 값도 갱신하도록 해봐야겠다.

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 코드트리