코딩 테스트(Coding Test)/백준

[백준] 14442번 : 벽 부수고 이동하기 2 - 자바(Java)

다문다뭉 2024. 11. 10. 22:50

Problem 🔒

문제

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

 

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

더보기

예제 입력 1

6 4 1
0100
1110
1000
0000
0111
0000

예제 출력 1

15

예제 입력 2

6 4 2
0100
1110
1000
0000
0111
0000

예제 출력 2

9

예제 입력 3

4 4 3
0111
1111
1111
1110

예제 출력 3

-1

 

Approach ❌

  1. 틀렸습니다(22%)
    • 최단 거리 초기화 값을 더 크게 잡았어야 했었다.
    • 최단 거리가 최대 1000*1000=1000000(백만)까지 나올 수 있는데 54321로 초기화했다.

Approach ⭕

  1. 변수 초기화 및 입력 처리
    • visit[r][c][broken]을 3차원으로 설정하여 (r,c) 위치에서 broken개의 벽을 부수고 도달한 경우 경로의 길이를 저장한다.
    • 0개(벽을 부수지 않고 이동한 경우)~K개(벽을 모두 부수고 이동한 경우)까지 총 K+1 크기가 필요하다.
  2. 시작점 초기화 설정
    • visit[0][0][0] = 1로 시작점에서 출발할 때의 경로 길이를 1로 설정한다.
    • 큐에 [0,0,0](현재 행, 현재 열, 부순 벽 개수)을 추가한다.
    • visit[0][0][1]~visit[0][0][K] 값을 1로 설정할 필요는 없다.(이미 최단 경로로 방문처리가 되어 있기 때문)
  3. BFS를 활용한 탐색
    • 큐에서 현재 위치(r,c)와 부순 벽의 개수(broken)를 가져온다.
    • 상,하,좌,우 4방향으로 이동할 좌표(nr,nc)가 유효한 범위 내에 있는지 검사한다.
      • 이동할 위치가 벽이고, 부순 벽의 개수가 K개 미만이고, 방문하지 않은 경우 벽을 부수고 이동한다.
      • 방문 검사를 진행할 때, visit[nr][nc][broken+1]을 확인해야 한다.
      • 벽을 부수고 이동한 경우, visit[nr][nc][broken+1]에 경로 길이를 저장하고, 큐에 추가한다.
      • 이동할 위치가 빈 칸이고, 방문하지 않은 경우 visit[nr][nc][broken]에 경로 길이를 저장하고, 큐에 추가한다.
  4. 결과 출력
    • 큐가 다 비었으면, 이동을 더이상 할 수 없다는 뜻이므로 최단 경로를 갱신한다.
    • 도착 지점(visit[N-1][M-1][i])에 벽을 i(0~K)개 부쉈을 때의 최단 경로가 저장되어 있으므로 최소 값을 갱신한다.
    • 도착 지점이 0이라면 방문할 수 없다는 뜻이므로 최소 값을 갱신하지 않는다.

Solution 💡

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 벽부수고이동하기2 {
    static int N, M, K, map[][], visit[][][], r, c, broken, nr, nc;
    static int[] dr={-1, 1, 0, 0}, dc={0,0,-1,1};
    static Queue<int[]> q = new LinkedList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); M = sc.nextInt(); K = sc.nextInt();
        map = new int[N][M]; visit = new int[N][M][K+1];
        for(int i=0; i<N; i++){
            String str = sc.next();
            for(int j=0; j<M; j++){
                map[i][j] = str.charAt(j) - '0';
            }
        }
        // 시작점 큐에 넣고, 방문처리
        q.add(new int[]{0,0,0});
        visit[0][0][0] = 1;
        int ans = BFS();
        System.out.println(ans==7654321?-1:ans);
    }

    public static int BFS(){
        int kan = 7654321;
        while(!q.isEmpty()){
            int[] get = q.poll();
            r = get[0];
            c = get[1];
            broken = get[2]; // 지금까지 벽을 몇 개 부쉈는지

            for(int d=0; d<4; d++){
                nr = r + dr[d];
                nc = c + dc[d];
                if(nr>=0 && nr<N && nc>=0 && nc<M){
                    // 벽이고, 지금까지 부순 벽 개수가 K개 미만이고, 방문하지 않았으면 벽 부수기
                    if(map[nr][nc]==1 && broken<K && visit[nr][nc][broken+1]==0){
                        visit[nr][nc][broken+1] = visit[r][c][broken] + 1;
                        q.add(new int[]{nr,nc,broken+1});
                    }
                    // 벽이 아니고, 방문하지 않았으면 이동하기
                    else if(map[nr][nc]==0 && visit[nr][nc][broken]==0){
                        visit[nr][nc][broken] = visit[r][c][broken] + 1;
                        q.add(new int[]{nr,nc,broken});
                    }
                }
            }
        }
        for(int i=0; i<K+1; i++){
            if(visit[N-1][M-1][i] == 0) continue;
            kan = Math.min(kan, visit[N-1][M-1][i]);
        }
        return kan;
    }//BFS
}

의문점 테스트 ⏱️

  1. 도착지점(N-1, M-1)에 도착했을 때, 최소 값을 갱신해주면 시간이 더 빨라질까?
    • 큐에서 꺼낸 현재 위치가 도착 지점이라면 최소 경로를 갱신한다.
    • 도착지점에 (K+1)번 도착했다면 루프를 종료한다.
    public static int BFS(){
  int kan = 7654321;
  int cnt = K+1;
  while(!q.isEmpty()){
      int[] get = q.poll();
      r = get[0];
      c = get[1];
      broken = get[2]; // 지금까지 벽을 몇 개 부쉈는지

      if(r==N-1 && c==M-1){
          if(visit[N-1][M-1][broken] == 0) continue;
          kan = Math.min(kan, visit[N-1][M-1][broken]);
          cnt--;
          if(cnt==0) break;
      }

      for(int d=0; d<4; d++){
          nr = r + dr[d];
          nc = c + dc[d];
          if(nr>=0 && nr<N && nc>=0 && nc<M){
              // 벽이고, 지금까지 부순 벽 개수가 K개 미만이고, 방문하지 않았으면 벽 부수기
              if(map[nr][nc]==1 && broken<K && visit[nr][nc][broken+1]==0){
                  visit[nr][nc][broken+1] = visit[r][c][broken] + 1;
                  q.add(new int[]{nr,nc,broken+1});
              }
              // 벽이 아니고, 방문하지 않았으면 이동하기
              else if(map[nr][nc]==0 && visit[nr][nc][broken]==0){
                  visit[nr][nc][broken] = visit[r][c][broken] + 1;
                  q.add(new int[]{nr,nc,broken});
              }
          }
      }
  }
  return kan;
}//BFS

  • 모든 이동을 마친 후, 최소 경로를 갱신하는 것이 더 빨랐다!
  • 도착 지점에 도착했을 때 최소 경로를 갱신하는 것은, 큐에서 현재 위치를 꺼낼때마다 도착 지점인지 검사해줘야 해서 더 느린것 같다.