[BOJ] 2178. 미로 탐색(BFS, DP)

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

 

알리바바와 40인 도둑 문제와 유사하다.

BFS와 DP를 적용하여 풀었는데

알리바바와 40인 도둑 문제를 풀어보면 느낌이 올 것이다.

#. Code

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

#include <cstdio> #include <queue> using namespace std; #define pos pair<int, int> #define x first #define y second   int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, 1, 0, -1 }; int Map[105][105], DP[105][105];   int main(void) {     int n, m, i, j;     // freopen("input.txt", "rt", stdin);     scanf("%d %d", &n, &m);       for (i = 1; i <= n; i++)          for (j = 1; j <= m; j++)              scanf("%1d", &Map[i][j]);              queue<pos> Q;     Q.push({ 1, 1 });     Map[1][1] = 0; DP[1][1] = 1;       while (!Q.empty()) {         pos now = Q.front();         Q.pop();           for (i = 0; i < 4; i++) {             int xx = now.x + dx[i];             int yy = now.y + dy[i];               if (Map[xx][yy]) {                 Q.push({ xx, yy });                 Map[xx][yy] = 0;                 DP[xx][yy] = DP[now.x][now.y] + 1;             }         }     }       printf("%d\n", DP[n][m]);       return 0; } Colored by Color Scripter

cs

line 19) 정수들이 붙어서 입력되어 "%1d" 로 받아야 한다.

line 22) 시작 지점을 Queue에 넣고,

line 23) 다시 올 일이 없으니 길을 0 으로 수정,

초기 위치 1칸 이동

line 25~39) Queue가 빌 때까지 반복

line 33~37) 길이 있으면

line 34) 해당 좌표를 queue에 넣고

line 35) 다시 돌아가면 안되므로 0으로 수정

line 36) 이동 칸 수는 이전 칸까지 이동한 칸 + 1