[ 백준 ] 2178번 - 미로 탐색 (C++)

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

2178번: 미로 탐색

 

 

[ 문제풀이 ]

 

매우 기본적인 bfs문제입니다. 방향 배열을 통해서 인접한 4방향으로 이동하고, visited배열을 통해서 방문을 체크해주면 됩니다. 지도에서 값이 1인 길일 때만 queue에 push 해주고, 방문을 한 번이라도 했다면 그 좌표는 무시해줍니다.

 

[ 소스코드 ]

#include<iostream>
#include<queue>
 
using namespace std;
 
struct node {
    int y;
    int x;
    int cnt;
};
 
int N, M;
char arr[100][101];
int visited[100][100];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++) {
        scanf("%s", arr[i]);
    }
 
    queue<node> q;
    q.push({ 0,0,1 });
 
    while (!q.empty())
    {
        int y = q.front().y;
        int x = q.front().x;
        int cnt = q.front().cnt;
        q.pop();
 
        if (y == N - 1 && x == M - 1) {
            printf("%d", cnt);
            return 0;
        }
 
        if (visited[y][x]) continue;
        visited[y][x] = 1;
 
        for (int i = 0; i < 4; i++) {
            int yy = y + dy[i];
            int xx = x + dx[i];
            if (yy >= 0 && yy < N && xx >= 0 && xx < M) {
                if (arr[yy][xx] == '1' && visited[yy][xx] != 1) {
                    q.push({ yy,xx,cnt + 1 });
                }
            }
        }
    }
}