[2178번] 미로 탐색

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. BFS :: http://www.crocus.co.kr/search/bfs

BFS 기본 문제이다.

방향을 설정해주는 dy, dx를 두고 (각 좌표를 보면 위, 아래, 왼쪽, 오른쪽으로 하나씩 설정되어있음을 알 수 있다.)

BFS를 돌려주면 된다.

이때 조건에는 ||를 통하여 다음 큐에 push되면 안되는 것들은 모두 배제 시키고 조건에 부합하는 것들만 push하여 큐를 최적화 시킨다.

그리고 마지막으로 y == n && x == m일때 출력하고 끝나는데 끝 지점에 첫번째로 도착하는 queue값이 당연히 최솟값이 된다는 것을 이용하였다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69

#include <iostream> #include <cstdio> #include <queue>   using namespace std;   typedef pair<int, int> pii;   int arr[102][102]; bool visit[102][102];   // 방향 설정 int dy[4] = { -1,0,1,0 }; int dx[4] = { 0,-1,0,1 };   int main() {     int n, m;     scanf("%d %d", &n, &m);       // %1d를 하면 숫자 하나씩만 받아들인다.     for (int i = 0; i < n; i++)         for (int j = 0; j < m; j++)             scanf("%1d", &arr[i][j]);       // 큐를 형성. y,x와 cnt를 담는 pair 형성한다.     queue<pair<pii, int>> q;       q.push({{ 0,0 }, 1});       while (!q.empty())     {         int y = q.front().first.first;         int x = q.front().first.second;         int cnt = q.front().second;           q.pop();           // 이미 방문했다면 continue         if (visit[y][x])             continue;           // 도착했다면 그 값 출력(출력하는 순간이 최소)         if (y == n - 1 && x == m - 1)         {             printf("%d", cnt);             break;         }           visit[y][x] = true;           // 조건에 부합되면 큐에 push하는 알고리즘         for (int i = 0; i < 4; i++)         {             int hereY = dy[i] + y;             int hereX = dx[i] + x;               if (hereY < 0 || hereY >= n || hereX < 0 || hereX >= m || visit[hereY][hereX] || !arr[hereY][hereX])                 continue;               q.push({ {hereY, hereX}, cnt + 1 });         }     }       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus