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

 

관련글

 

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

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

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

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

 

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

 

 

2. 풀이

 

이는 주변 위치를 탐색하며 최대한 빠르게 도달할 수 있는 경우를 찾는 문제이므로 BFS로 해결할 수 있다.

 

모든 위치는 2가지 경우가 있다. 벽을 깨면서 도달하거나 그냥 도달하거나의 2가지 이다.

즉, 각 위치 정보만이 아닌 벽을 깨서 도달했는지에 대한 여부 또한 저장할 수 있어야 한다.

 

이를 3차원 배열로 만들어서 수행하였다. X, Y의 위치 정보와 벽을 깨거나 깨지 않거나의 2가지를 저장할 수 있는 3차원 배열을 통해 이미 탐색 여부를 확인할 수 있도록 코드를 작성하였다.

 

 

3. 코드

 

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

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

public class Main{
    static int n, m;
    static int[][] map;
    static int[][][] move;
    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());
        map = new int[n][m];
        move = new int[n][m][2];
        
        for(int i=0; i < n; i++){
            String line = br.readLine();
            for(int j=0; j < m; j++){
                map[i][j] = line.charAt(j) - '0';
            }
        }
        bfs();
        
        // 벽을 1개 깨거나 안깨거나 도달할 수 없는 경우
        if(move[n-1][m-1][0] == 0 && move[n-1][m-1][1] == 0){
            System.out.println(-1);
        // 도달이 가능한 경우, 더 작은 숫자를 출력
        } else {
            if(move[n-1][m-1][0] == 0) {
                System.out.println(move[n-1][m-1][1]);
            } else if(move[n-1][m-1][1] == 0){
                System.out.println(move[n-1][m-1][0]);
            } else {
                int min = Math.min(move[n-1][m-1][0], move[n-1][m-1][1]);
                System.out.println(min);
            }
        }
        
        br.close();
    }
    
    private static void bfs(){
        // 제일 첫 위치의 경우는 벽을 깨지 않고 (0, 0)으로 탐색하는 경우임
        // 첫 위치를 탐색하는 것도 1회로 결정해야 하므로 1로 설정
        move[0][0][0] = 1;
        Queue<Pos> q = new LinkedList<>();
        q.offer(new Pos(0, 0, 0));
        
        while(!q.isEmpty()){
            Pos c = q.poll();
            
            // 목적 위치에 도달한 경우 반환
            if(c.y == n-1 && c.x == m-1) return;
            
            for(int i=0; i < 4; i++){
                int ny = c.y + dy[i];
                int nx = c.x + dx[i];
                
                // 범위 밖으로 나간 경우 다음 탐색 수행
                if(ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
                
                // t는 벽인지 빈 칸인지를 확인하기 위해 가져오는 수
                int t = map[ny][nx];
                
                // 0이 아니라면 이미 이전에 방문을 했던 것이므로 넘어간다.
                if(move[ny][nx][t] != 0) continue;
                
                // 이전 위치가 벽을 아직 깬 적이 없는 경우
                if(c.m == 0){
                    // 다음 위치가 벽이건 아니건 탐색
                    move[ny][nx][t] = move[c.y][c.x][c.m] + 1;
                    q.offer(new Pos(ny, nx, t));
                } else {
                    // 다음 위치가 빈 칸인 경우에만 탐색
                    if(t == 0 && move[ny][nx][1] == 0){
                        move[ny][nx][1] = move[c.y][c.x][c.m] + 1;
                        q.offer(new Pos(ny, nx, 1));
                    }
                }
            }
        }
    }
}

class Pos{
    int y;
    int x;
    int m;
    public Pos(int y, int x, int m){
        this.y=y;
        this.x=x;
        this.m=m;
    }
}

 

 

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