Baekjoon 2178번 미로 탐색

문제

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

걸린 시간

00 : 43 : 21

풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

int n, m;
int maze[100][100];
int visited[100][100];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};

int bfs(){
    queue<pair<int, int>> q;
    q.push(make_pair(0, 0));
    int ans = 0;
    while(!q.empty()){
        ans++;
        int s = q.size();
        for(int i = 0; i < s; i++){
            auto tmp = q.front();
            int x = tmp.first;
            int y = tmp.second;
            q.pop();
            if(x == n-1 && y == m-1)
                return ans;
            for(int j = 0; j < 4; j++){
                int nx = x + dx[j];
                int ny = y + dy[j];
                if(0 <= nx && nx < n && 0 <= ny && ny < m && maze[nx][ny]){
                    if(!visited[nx][ny]){
                        visited[nx][ny] = 1;
                        q.push(make_pair(nx, ny));
                    }
                }
            }

        }
    }
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            scanf("%1d", &maze[i][j]);
    memset(visited, 0, sizeof(visited));
    printf("%d\n", bfs());
    return 0;
}

지겨운 그래프 이론 문제. 그래도 얻어갈 건 조금 있었다.

1. 붙어 있는 문자가 입력으로 들어올 땐 "%1d" 를 사용하면 된다.
2. bfs 구현에 사용한 for 문의 반복 조건을 .size() 메소드로 직접 접근하면 계속해서 값이 갱신되기 때문에 잘못된 결과가 나온다.