백준 문제번호 - 미로탐색 - BFS

문제

문제링크 : https://www.acmicpc.net/problem/2178

풀이전략

1. 단순히 최단길이를 찾는 문제이다.
   
   다른 블로그에서 퍼온 내용인데, 이러한 이유로 최단 길이 경로를 보장하는 BFS를 최단거리를 찾는 문제에서는 항상 적용한다.

• BFS는 순차적으로 queue에 해당칸을 넣기 때문에 당연히 최단 길이 경로를 보장한다

2. 가로 세로만 이동하기 때문에 dy, dx배열을 만들어서 해결한다.

코드

#include<bits/stdc++.h>

using namespace std;

int N, M;
// 지난 값들을 저장하는 부분
int check[100][100] = {0, };
//  한번 지나간 부분은 다시 지나가지 않기 위함
bool v[100][100] = {false,};
// char array로 해도 되는데 왜 굳이 string으로 했었는지 모르겠다.
string arr[100];
// 이동부분
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

void BFS(int i, int j){
    v[i][j] = true;
	/// queue에 pair를 만들어 r,c를 저장해줌.
    /// 이후 거리는 check에 저장해줌
    queue<pair<int, int> > q;
    q.push(make_pair(i, j));

    while(!q.empty()){
        int x = q.front().second;
        int y = q.front().first;

        q.pop();

        for(int k=0; k<4; k++){
            int newX = x+dx[k];
            int newY = y+dy[k];
            if(0 <= newX && newX < M && 0 <= newY && newY < N && arr[newY][newX] == '1' && !v[newY][newX] && check[newY][newX] == 0){
                check[newY][newX] = check[y][x] + 1;
                v[newY][newX] = true;
                q.push(make_pair(newY, newX));
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    int i;

    cin >> N >> M;
    for(i=0; i<N; i++) cin>> arr[i];

    BFS(0,0);
    cout<<check[N-1][M-1]+1<<endl;

    return 0;
}

소감

사실 문제를 다시보니 그냥 단순하게 struct을 선언하여 문제를 풀었으면 더 쉬웠을 텐데 아무래도 첫 문제였기 때문에 이 방법은 시행착오였던거 같다. 이렇게 바보같이 풀었던 때를 기억하며 그 뒤에 문제에서 나아지는 내모습을 보자.