[C++] 백준 1261 : 알고스팟

문제

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

 

 

 

풀이 방법

0-1 BFS를 이용하여 풀 수 있는 문제였다.

1. 벽을 부수지 않고 이동할 수 있는 경우 dq.push_front() 를 이용해 deque의 앞에 다음 위치 삽입
2. 벽을 부숴야 이동할 수 있는 경우 dq.push_back()을 이용해 deque의 뒤에 다음 위치 삽입

 

이를 통해 벽을 부수지 않는 방법에 대한 우선순위를 고려할 수 있다. 

 최대한 벽을 부수지 않고 이동해야 부숴야 하는 벽의 최소 개수를 구할 수 있기 때문에, 벽을 부수지 않고 이동하는 것을 우선적으로 고려해야 한다. 즉 벽을 부수지 않고 이동하는 경우를 dq에서 먼저 빼야 한다.

 

이때 방문 표시를 해가며 이미 방문한 위치는 다시 방문하지 않도록 한다.

 

 

코드

#include <iostream>
#include <deque>
using namespace std;

int n,m;
int maze[101][101];
int visited[101][101];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

struct State{
    int c_x, c_y, c_w;
};

void bfs(){
    deque<State> dq;
    dq.push_back({0,0,0});
    visited[0][0]=1;
   
    while(!dq.empty()){
        State cur = dq.front();
        dq.pop_front();
        
        // 목표지점에 도달한 경우
        if(cur.c_x == m-1 && cur.c_y == n-1){
            cout << cur.c_w;
            return;
        }
      
        // 다음 위치로 이동
        for(int i=0; i<4; i++){
            int nx = cur.c_x + dx[i];
            int ny = cur.c_y + dy[i];
            
            // 범위를 벗어난 경우
            if(nx < 0 || nx >=m || ny <0 || ny >=n) continue;
            
            // 이미 방문한 곳인 경우
            if(visited[nx][ny]==1) continue;
            
            // 벽을 부수지 않아도 되는 경우
            if(maze[nx][ny]==0){
                dq.push_front({nx,ny,cur.c_w});
                visited[nx][ny]=1;
            } 
            
            // 벽을 부숴야 하는 경우
            else{
            	
                // 필요한 벽의 개수 증가시키고 dq의 back에 삽입
                dq.push_back({nx,ny,cur.c_w+1});
                visited[nx][ny]=1;
            } 
        }
    }
    
}

int main()
{
    cin >> n >> m;
    for(int i=0; i<m; i++){
        string line;
        cin >> line;
        for (int j = 0; j < n; j++) {
            maze[i][j] = line[j] - '0';  // 문자 '0'을 빼서 숫자로 변환
        }
    }
    
    bfs();
    return 0;
}

 

 

메모

 입력 받을 때 공백으로 구분해서 주어지는지, 아닌지를 이용해 입력받을 방식을 결정해야 한다. 이 경우 공백 없이 입력받기 때문에 string으로 입력받은 후 각각 숫자로 변환해주어야 한다.