[c++/알고리즘] 백준 2178 미로탐색:BFS

최소 칸의 수를 구한다 -> BFS를 사용하여 푼다

시간초과가 떠서 왜이러지 했던 문제...

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// (1,1)에서 (n,m)으로 갈 때 지나야하는 최소의 칸수 구하기
int ch[101][101];
int main(){
    int n, m, num, x, y, cnt=0;
    int map[101][101];
    int pos[4] = {0, 1, 0 , -1}; // 방향배열 시계방향
    int pos2[4] = {1, 0, -1, 0};
    queue<pair<int, int>> Q;

    cin >> n >> m;

    // 시간초과는 해결
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%1d", &map[i][j]);
        }
    }
    
    Q.push(make_pair(1,1));
    ch[1][1] = 1;

    while(!Q.empty()){
        x = Q.front().first;
        y = Q.front().second;
        Q.pop();

        for(int i=0; i<4; i++){
        	
            // 범위를 벗어날 경우 continue;
            if (x+pos[i] < 1 || x+pos[i] >n || y+pos2[i] > m || y+pos2[i] < 1) continue;
            
            // 배열을 한번도 지나온 적이 없고, 이동할 수 있는 경로인 경우
            if(ch[x+pos[i]][y+pos2[i]] == 0 && map[x+pos[i]][y+pos2[i]] == 1){
            	// 체크배열에 현재 이동한 횟수를 더한다.
                ch[x+pos[i]][y+pos2[i]] =  ch[x][y] + 1;
                Q.push(make_pair(x+pos[i], y+pos2[i]));
            }

            if( x+pos[i] == n && y+pos2[i] == m){
                cout << ch[x+pos[i]][y+pos2[i]]  << endl;
                return 0;
            }

        }
    }
    return 0;
}

1. 배열을 입력받을때 시간초과가 났다.
   N행의 요소가 붙어서 입력으로 주어져서 이를 처음에는

for(int i=1; i<=n; i++){
        cin >> num;
        for(int j=m; j>=1; j++){
            map[i][j] = num%10;
            num /= 10;
        }
    }

이렇게 각 자릿수를 나누어서 배열에 나누려고 했는데.. 시간초과가 났다. 흠.. 시간복잡도 공부를 해야한다.

그래서 수정한 코드

for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%1d", &map[i][j]);
        }
    }

한자리씩 입력받아서 배열에 넣는다.