✅ BFS ✅ 최단거리 ✅ 문자열 배열 탐색시 인덱스 값 유의

문제

링크

풀이

최소거리를 구하는 문제이므로 BFS를 이용한다.
그리고 방문하지 않은 곳만 방문하도록 하면 최초에 방문한 거리가 가장 짧은 거리가 된다.

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>

using namespace std;

int N, M;
string map[102];
queue<pair<int, int>> que;
int dist[102][102];

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

void BFS(){
    while(!que.empty()){
        int y = que.front().first;
        int x = que.front().second;
        que.pop();
        
        if(y == N-1 && x == M-1){
            cout << dist[y][x] << "\n";
            return;
        }
        
        for(int i=0;i<4;i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            
            if(ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
            if(map[ny][nx] == '0') continue;
            if(dist[ny][nx] != 0) continue;
            
            que.push({ny,nx});
            dist[ny][nx] = dist[y][x] + 1;
        }
        
    }
    
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> N >> M;
    
    for(int i=0;i<N;i++){
        cin >> map[i];
    }
    
    que.push({0,0});
    dist[0][0] = 1;
    
    BFS();

    return 0;
}

중요한점

문제에 시작 좌표가 (1,1) 도착 좌표가 (N,M)이라고 해서
(1,1) 부터 (N,M)까지 탐색하여 풀었다. 하지만 그러면 틀린답이 나온다.

왜냐하면 입력을 문자열의 배열로 받았기 때문에 y값은 1부터 입력 받았으므로 1부터 탐색해도 되지만, x값은 문자열의 인덱스 시작값인 0부터 탐색해야 하므로 1부터 탐색하면 틀린 값이 나온다.