백준 2178 미로 탐색, c++

 

 

처음 작성한 코드는 다음과 같다.

#include <iostream>
#include <string>
#include <queue>
using namespace std;

int N, M;
string str;
int arr[101][101];
int visited[101];
queue<int> q;

void bfs(int k) {
    q.push(k);
    while(!q.empty()) {
        k = q.front();
        q.pop();
        for(auto i=1; i<=N; i++) {
            if(arr[k][i]!=0 && !visited[i]) {
                q.push(i);
                visited[i]=visited[k]+1; 
            }
        }
    }
}

int main() {
    //필요한 수 입력받아 저장하기
    cin >> N >> M;
    for(int i=1; i<=N; i++) {
        cin >> str;
        for(int j=1; j<=M; j++) {
            arr[i][j] = static_cast<int>(str[j]-48);
        }
    }
    
    //(1,1)부터 (N,M)까지의 최단거리 구하기
    bfs(1);
    
    //출력하기
    cout << visited[M];
    
    return 0;
}

 

하지만 이번 문제에서는 정점끼리의 간선연결이 아닌, 2차원 배열 형태(인접행렬? 형태)로 주어지기 때문에 이에 맞게 코드를 바꿔야했다.

bfs 알고리즘을 인자를 두개를 받아와 2차원 배열 형태로 bfs알고리즘을 고려하도록 구현해야 했다.

이 문제 형태도 익숙하게 만들어서 약간의 변형이 있을 때 해결할 수 있도록 해야겠다.