알고리즘 풀이 - 백준 1261(알고스팟, 그래프(BFS))

 

관련글

 

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

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

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

 

NxM 크기의 미로에 (1, 1) → (N, M)으로 이동하고자 한다면 벽을 최소 몇 개를 부셔야 하는지 구하는 문제

 

 

2. 풀이

 

이 문제는 NxM 크기의 미로에 벽과 벽이 아닌 곳이 있으므로 각 위치를 그래프 형태로 탐색만 수행하면 된다.

 

탐색은 최소의 경우를 구하는 문제이므로 BFS로 탐색을 수행한다. 하지만 벽으로 연결되지 않은 부분 부터 모두 탐색을 완료하고 벽이 있는 부분을 탐색 해야 한다.

왜냐하면, 아래와 같은 예외 상황이 있을 수 있기 때문이다.

 

위와 같이 빨간색으로 이동 시에는 벽을 3개를 부수어야 하지만, 파란색으로 이동 시에는 벽을 부수지 않고도 지나갈 수 있다.

그런데, BFS의 탐색 상, 어느 방향을 먼저 탐색하느냐에 따라 그 결과가 다를 수 있기 때문에 항상 파란색이 정답이 된다고 보장할 수 없다.

 

따라서, 벽이 없는 쪽을 우선 탐색하도록 자료구조를 구성하거나 알고리즘을 구성하여야 한다. 여기서는 Deque를 이용하여 벽이 없는 곳은 탐색 우선 순위로 하여 탐색을 수행하였다.

 

 

3. 코드

 

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Deque;
import java.util.LinkedList;

public class Main{
    static int n;
    static int m;
    static int[][] maze;
    static boolean[][] visited;
    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));
        String[] line = br.readLine().split(" ");
        
        // ************* 그래프 초기화 ************
        n = Integer.parseInt(line[0]);
        m = Integer.parseInt(line[1]);
        maze = new int[m][n];
        visited = new boolean[m][n];
        for(int i=0; i < m; i++){
            String s = br.readLine();
            for(int j=0; j < n; j++){
                maze[i][j] = s.charAt(j) - '0';
            }
        }
        
        // ****************************************
        
        
        // ************** Deque를 사용하여 현재 방문 위치 저장 및 탐색 ****************
        Deque<Pos> q = new LinkedList<>();
        q.offer(new Pos(0, 0, 0));
        visited[0][0] = true;
        int ans = 0;
        while(!q.isEmpty()){
            // 벽이 아닌 곳부터 모두 탐색 완료 해야 함
            Pos u = q.pollLast();
            if(u.y == m-1 && u.x == n-1) {
                ans = u.crash;
                break;
            }
            
            for(int i=0; i < 4; i++){
                int ny = u.y+dy[i];
                int nx = u.x+dx[i];
                
                if(0 <= ny && ny < m && 0 <= nx && nx < n && !visited[ny][nx]){
                    visited[ny][nx] = true;
                    
                    // 1은 벽 - 벽은 앞쪽에 추가
                    if(maze[ny][nx] == 1){
                        q.addFirst(new Pos(ny, nx, u.crash+1));
                    // 0은 길 - 길은 뒤쪽에 추가
                    } else {
                        q.addLast(new Pos(ny, nx, u.crash));
                    }
                }
            }
        }
        System.out.println(ans);
        br.close();
    }
}
class Pos{
    int y;
    int x;
    int crash;
    public Pos(int y, int x, int crash){
        this.y = y;
        this.x = x;
        this.crash = crash;
    }
}

 

 

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