[13565번] 침투

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. BFS

전형적인 BFS 문제이다.

BFS 문제에서 응용이라고 한다면, outer side -> inner side로 잘 들어가는지 확인해줘야 한다는 것이다.

결국 outer side가 될 수 있는 부분인 (x,0) 부분들을 차례로 queue에 넣어주며 bfs를 돌린 후, 그 bfs의 과정속에 

y 값이 n - 1로 도착할 수 있다면 inner side로 잘 도착했다는 의미가 된다.

소스 코드 : 

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 70 71 72 73

#include <iostream> #include <cstdio> #include <queue>   using namespace std;   typedef pair<int, int> pii;   int arr[1011][1011]; bool visit[1011][1011];   int dy[4] = { 1,0,-1,0 }; int dx[4] = { 0,1,0,-1 };   int main() {     int n, m;     scanf("%d %d", &n, &m);       for (int i = 0; i < n; i++)         for (int j = 0; j < m; j++)             scanf("%1d", &arr[i][j]);       queue<pii> q;       for(int i = 0 ; i < m ; i ++)     {         if (arr[0][i] == 1)             continue;           q.push({ 0,i });           while (!q.empty())         {             int x = q.front().second;             int y = q.front().first;               q.pop();               if (visit[y][x])                 continue;               visit[y][x] = true;               for (int j = 0; j < 4; j++)             {                 int nx = x + dx[j];                 int ny = y + dy[j];                   if(!(0 <= ny && ny < n) || !(0 <= nx && nx < m) || visit[ny][nx])                     continue;                   if(arr[ny][nx] != 1)                 {                     if (ny == n - 1)                     {                         printf("YES");                         return 0;                     }                       q.push({ ny,nx });                 }             }         }     }       printf("NO");       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus