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

 

관련글

 

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

 

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

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

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

 

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

 

 

2. 풀이

 

기본적으로 각 정점을 방문 시 최단 거리로 방문 가능한 경우를 찾는 문제이므로 BFS(그래프 탐색)으로 해결할 수 있다.

우선 K개의 벽을 부술 수 있다는 부분을 유의하여 해결해야 한다.

 

목표 지점을 제외한 모든 정점을 탐색 시에, 0~K-1개의 벽을 부수어 방문이 가능하다.

초기에 생각은 Y, X의 위치와 부순 벽의 수를 저장하는 3차원 배열을 만들어 BFS를 수행하면 될 것으로 생각했으나, 그 경우 메모리 초과가 발생한다.

 

따라서, 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];  // 2차원 배열로 Map 정보 저장
        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';
            }
        }
        
        // BFS 탐색을 통해 결과를 가져온다.
        int ans = bfs();

        System.out.println(ans);
        br.close();
    }

    private static int bfs(){
        Queue<Pos> q = new LinkedList<>();
        
        // 최초 위치는 (0, 0)이며, 현재 부순 벽은 0개, 이동 횟수는 1로 하여 최초 위치 Queue 삽입
        q.offer(new Pos(0, 0, 0, 1));
        
        // 각 위치별로 부순 벽의 수를 저장하는 2차원 배열
        int[][] visited = new int[n][m];
        
        // 최초에는 Int중 최대값으로 초기화
        for(int i=0; i < n; i++){
            Arrays.fill(visited[i], Integer.MAX_VALUE);
        }
        
        // 0, 0은 부수는 벽이 없으므로 0으로 초기화
        visited[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 || visited[ny][nx] <= c.w) continue;
                
                // 해당 위치가 벽일 때,
                if(map[ny][nx] == 1){
                    // 최대 부술 수 있는 벽의 수가 K이므로 이미 부순 벽의 수가 그보다 적으며
                    // 해당 위치를 이전 까지의 탐색에서 더 많은 벽을 부수며 탐색한 경우
                    if(c.w < k && visited[ny][nx] > c.w+1){
                        // Queue에 넣고 벽을 부순 횟수 갱신
                        q.offer(new Pos(ny, nx, c.w+1, c.m+1));
                        visited[ny][nx] = c.w+1;
                    }
                // 벽이 아닌 경우
                } else {
                    // 무조건 탐색 수행
                    // Queue에 넣고 벽을 부순 횟수 갱신
                    q.offer(new Pos(ny, nx, c.w, c.m+1));
                    visited[ny][nx] = c.w;
                }
            }
        }
        return -1;
    }
}

class Pos{
    int y;  // Y 위치
    int x;  // X 위치
    int w;  // 부순 벽의 수
    int m;  // 이동한 횟수
    public Pos(int y, int x, int w, int m){
        this.y=y;
        this.x=x;
        this.w=w;
        this.m=m;
    }
}

 

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