알고리즘 풀이 - 백준 16933(벽 부수고 이동하기 3, 그래프(BFS))

 

관련글

 

그래프 관련 포스팅은 여기를 참조
DFS 관련 포스팅은 여기를 참조
BFS 관련 포스팅은 여기를 참조

관련 문제인 벽 부수고 이동하기 관련 포스팅은 여기를 참조
관련 문제인 벽 부수고 이동하기4 관련 포스팅은 여기를 참조
관련 문제인 벽 부수고 이동하기2 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

NxM의 맵에서 0은 이동 가능, 1은 벽일 때, (0, 0)에서 (N-1, M-1) 위치까지 낮에만 벽을 최대 K개 부수어 도달 시 가장 최단으로 도달 가능한 경우를 구하는 문제

 

 

2. 풀이

 

이 문제는 벽 부수고 이동하기 2(여기 참조) 와 유사한데 낮 / 밤의 개념이 추가되어 낮에만 벽을 부술 수 있는 경우를 고려해야 하는 문제이다.

 

우선 벽을 최대 K개 만큼 부술 수 있기 때문에 3차원의 배열로 탐색 위치(Y, X)와 벽을 부순 횟수를 저장하여 탐색하고자 생각할 수 있다.

그러나 이 경우 메모리 초과 문제가 발생하게 된다. 따라서, Y, X의 위치값에 따라 해당 위치에 도달하기 까지 벽을 몇 개 부수었는지 2차원 배열로 저장하는 방식으로 문제를 해결하였다.

 

각 위치는 벽을 부순 횟수에 따라 여러 번 방문 될 수 있다. 이 때, 이미 이전에 탐색하며 부순 벽의 횟수가 더 적다면 추가 탐색을 하지 않는 식으로 중복 탐색을 방지할 수 있다.

벽을 더 많이 부수면 무조건 더 빠르게 도달할 수 있기 때문에 이후에 방문 시에는 반드시 더 적게 벽을 부순 경우만 체크하면 되기 때문이다.

 

여기에 추가로 낮에만 벽을 부술 수 있으므로 이전 정점 탐색 시에 해당 시간대가 낮인지, 밤인지를 저장하는 부분을 추가한다.

이를 통해, 현재 낮이라면 벽을 부술 수 있고 아니라면 벽을 부술 수 없다고 판단하며 탐색을 수행하면 문제를 해결할 수 있다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

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

public class Main{
    static int n, m, k;
    static int[][] map;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, -1, 0, 1};
    
    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());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        
        map = new int[n][m];
        for(int i=0; i < n; i++){
            String s = br.readLine();
            for(int j=0; j < m; j++){
                map[i][j] = s.charAt(j) - '0';
            }
        }
        int ans = bfs();
        System.out.println(ans);
        br.close();
    }
    
    private static int bfs(){
        // 각 위치에 부순 벽의 수를 기입하는 배열
        int[][] broken = new int[n][m];
        for(int i=0; i < n; i++){
            Arrays.fill(broken[i], Integer.MAX_VALUE);
        }
        Queue<Pos> q = new LinkedList<>();
        
        // 처음 위치 - 낮 시간대로 설정
        q.offer(new Pos(0, 0, 0, 1, true));
        broken[0][0] = 0; // 최초 위치에서 부순 벽의 수는 0개
        
        int ny, nx;
        while(!q.isEmpty()){
            Pos c = q.poll();
            if(c.y == n-1 && c.x == m-1) {
                return c.m;
            }
            
            for(int i=0; i < 4; i++){
                ny = c.y + dy[i];
                nx = c.x + dx[i];
                
                // 범위를 벗어났거나 이미 부순 벽의 수가 더 많다면 넘어간다.
                if(ny < 0 || ny >= n || nx < 0 || nx >= m || broken[ny][nx] <= c.w) continue;
                // 벽의 위치라면
                if(map[ny][nx] == 1){
                    // 최대 부술 수 있는 벽을 이미 다 부순 경우는 진행 불가
                    if(c.w >= k) continue;
                    
                    // 현재 정점이 낮인 상태여야 하며, 현재 벽을 부순 횟수가 최대보다 더 작은 경우
                    if(c.d){
                        broken[ny][nx] = c.w+1;
                        // Queue에 삽입
                        q.offer(new Pos(ny, nx, c.w+1, c.m+1, false));
                    // 만약 현재 정점이 밤인 상태라면, 낮이 될 때를 대기하여 기다린다.
                    } else {
                        q.offer(new Pos(c.y, c.x, c.w, c.m+1, true));
                    }
                // 벽이 아니라면
                } else {
                    // 부순 벽의 횟수 업데이트
                    broken[ny][nx] = c.w;
                    
                    // 다음 탐색 지점의 낮/밤 여부 지정
                    boolean day = c.d ? false : true;
                    q.offer(new Pos(ny, nx, c.w, c.m+1, day));
                }
            }
        }
        return -1;
    }
}

class Pos{
    int y; // 행 위치
    int x; // 열 위치
    int w; // 부순 벽의 수
    int m; // 이동 횟수
    boolean d; // 낮 밤 여부
    public Pos(int y, int x, int w, int m, boolean d){
        this.y=y;
        this.x=x;
        this.w=w;
        this.m=m;
        this.d=d;
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.