백준(C++) 2178 [미로탐색]

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

접근방법

미로탐색 문제는 너비 우선 탐색을 이용하여 푸는 문제이다. 너비 우선 탐색(BFS)는 모든 길을 한번 씩 다 탐색한 후 다시 연결된 길을 넓게 탐색하는 방법이다.

보통 주어진 그래프에서 시작점과 끝점이 있을때 최단경로를 알고 싶을떄 사용한다.

미로라는 board 배열과 모든 가야될 길을 넣을 queue와 조건문을 사용하여 코딩했다.

조건은 board배열 밖으로 나가는 경우, 벽에 닿을 경우, 최단 경로가 아닌 경우 로 설정했다.

이동은 dx,dy 함수를 사용하여 동서남북을 구현했다.

이 BFS의 끝은 더이상 갈곳이 없을때, 즉 큐가 비어있을때 종료하도록 했다.

매우 기초적인 문제이기에 쉽게 풀었다.

 

코드는 다음과 같다.

#include<iostream>
#include<queue>

using namespace std;
    string board[502];
    int is[502][502];
    int xx,yy; 
    int dx[4] = {1 ,0 ,-1, 0};
    int dy[4] = {0 ,1 , 0 ,-1};
    

    int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> xx >> yy;
    
    
    for(int a=0;a<xx;a++)
            cin >> board[a];
    for(int a=0;a<xx;a++)fill(is[a],is[a]+yy,-1);
                queue<pair<int, int> > q;
                is[0][0] = 0;
                q.push({0,0});
            while(!q.empty()){
                auto cur = q.front();q.pop();
                for(int dir =0; dir < 4;dir++){
                    int nx = cur.first+x[dir];
                    int ny = cur.second+y[dir];
                    if(nx < 0 || nx >=xx || ny <0 || ny >= yy) continue;
                    if(is[nx][ny] >= 0 || board[nx][ny] != '1' )continue;
                    is[nx][ny] = is[cur.first][cur.second]+1;
                    q.push({nx,ny});
                    
                }
            }
        
    
            cout << is[xx-1][yy-1]+1<<'\n';

    return 0;
        }