[백준 2178] 알고리즘 84일차 : 미로탐색

www.acmicpc.net/problem/2178

2178번: 미로 탐색

C++ BFS

즐거운 미로탐색

갈수있는 길이 2차원 배열로 주어지고 0,0에서 n-1,m-1까지의 최단'거리'를 구하는 문제

경로가 아니라 인덱스를 저장할 필요는 없다 (parent배열 안갖고 있어도 된다는 소리)

 

접근방법

여느 BFS와 같이 큐에 인접한 노드를 저장하고 (여기서는 인접한 노드가 길이 있으며(maze배열에서 1), 아직 방문하지 않음(distances가 -1)) 동시에 인접한 노드들의 distances를 갱신하고 

또 큐에서 인출하고 이 과정 반복(큐가 빌때까지)

 

오답노트

상하좌우 돌면서 인접한 노드 저장할때 현재 위치가 1행, 1열에 있는 노드일때는 한칸씩 범위가 넘어가게 되는데

이제까지는 처리 안해줘도 돌아갔는데 vector라 그런지 런타임에러가 났었다. 그래서 인접노드 저장할때 범위체크도 해줌 >=0)

원래는 parent배열도 썼었는데 코드 제출하고 보니까 here로 충분히 처리 가능한 것 같아서 뺐다.

(잘 돌아감 경로를 출력하는게 아니라 빼도 된다.)

 

단순 BFS까지는 무리없이 짰는데 최단경로 부분을 완벽히 습득하진 못한 것 같다.

다시 공부 하도록

 

소스코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int dr[4] = {0,0,1,-1};
int dc[4] = {1,-1,0,0};
vector<vector<int>> distances(101,vector<int>(101,0));
queue<pair<int, int>> q;
vector<vector<int>> maze(105,vector<int>(105));

int main(){
    int n,m;
    char is;
    cin >> n >> m;
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < m ; j++){
            cin >> is;
            maze[i][j] = is-'0';
        }
    }
    
    distances[0][0] = 1;
    q.push(make_pair(0, 0));
    while(!q.empty()){
        pair<int,int> here = q.front();
        q.pop();
        for(int i = 0 ; i < 4 ; i++){
            int cr = here.first+dr[i];
            int cc = here.second+dc[i];
            if(cr >= 0 && cc >= 0 && distances[cr][cc] == 0 && maze[cr][cc]){
                q.push(make_pair(cr, cc));
                distances[cr][cc] = distances[here.first][here.second] + 1;
            }
        }
    }
    cout << distances[n-1][m-1];
    return 0;
}