[Inflearn] 미로탐색(DFS)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

     - 7 * 7 격자판 미로 탈출 경로의 가지수

     - 출발점은 (1,1), 도착점은 (7,7)

     - 격자판 1은 벽, 0 은 통로

     - 상하좌우로만 이동

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

      - DFS

  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

격자는 상,하,좌,우 로 이동할 수 있다고 했다.

출발지점부터 편하게 상, 하, 좌, 우 이렇게 접근해보자

먼저 과정을 스택에 쌓으면서 그려보자.

(1,1) 부터 출발해보자.

D(1, 1)

D(x, y-1)    // 상

D(x, y+1)    // 하

D(x-1, y)    // 좌

D(x+1, y)    // 우

하단으로 먼저 갈 것이므로 D(x, y+1) 로 호출해보자.

D(1, 2)

D(1, 1)

...

D(1, 3)

D(1, 2)

D(1, 1)

하단으로 더이상 갈 수 없다면, 

return을 해주어야 할 것이다.

if(map[x][y] == 1)

return;

if(x > n || y > n )

return;

else

{

D(x, y-1)    // 상

D(x, y+1)    // 하

D(x-1, y)    // 좌

D(x+1, y)    // 우

}

지금 상태에서 상, 하, 좌 가 모두 안 되므로,

우측으로 이동한다.

D(3, 3)

D(2, 3)

D(1, 3)

D(1, 2)

D(1, 1)

여기서 의문이, 이미 왔던 길을 어떻게 판별할지인데,

이미 왔던 길은 1로 체크하는 것이 좋을 듯 하다.

if(map[x][y] == 1)

return;

if(x > n || y > n )

return;

else

{

map[x][y] = 1;

D(x, y-1);    // 상

D(x, y+1);    // 하

D(x-1, y);    // 좌

D(x+1, y);    // 우

map[x][y] = 0;

}

이렇게되면 다음으로 좌측은 이미 지나간 길이라 1일테고, 하단으로 가겠군

D(3, 4)

D(3, 3)

D(2, 3)

D(1, 3)

D(1, 2)

D(1, 1)

...

이 과정으로 코딩해보면 될것 같다.

if(map[x][y] == 1)

return;

if(x > n || y > n || x < 1 || y < 1)

return;

else if(x == n && y == n)

cnt++;

else

{

map[x][y] = 1;

D(x, y-1);    // 상

D(x, y+1);    // 하

D(x-1, y);    // 좌

D(x+1, y);    // 우

map[x][y] = 0;

}

#. 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 45 46 47 48 49

#include <cstdio> #include <vector> #include <algorithm>   using namespace std;   int map[8][8], cnt = 0;   void DFS(int x, int y) {     if (map[x][y] == 1)         return;       if (x > 7 || y > 7 || x < 1 || y < 1)         return;     else if (x == 7 && y == 7)         cnt++;     else     {         map[x][y] = 1;           DFS(x, y - 1);         DFS(x, y + 1);         DFS(x - 1, y);         DFS(x + 1, y);           map[x][y] = 0;     } }   int main(void) {     freopen("input.txt", "rt", stdin);       int i,j ;       for (j = 1; j <= 7; j++)     {         for (i = 1; i <= 7; i++)             scanf("%d", &map[i][j]);     }       DFS(1, 1);       printf("%d\n", cnt);       return 0; } Colored by Color Scripter

cs

와아아.. 이번에는 스택으로 그리면서 코드를 만들어나가니깐

한 번에 성공했다..!

비록 쉬운 문제일지라도 나에겐 헷갈리고 복잡했던 재귀함수를 이제 어느정도 이해할 수 있을 것 같다.

이런 기분으로 PS를 하는구나.. 캬캬캬

앞으로는 DFS 문제는 스택을 그려보면서 함수를 만들어나가도록 해야겠다!

line 11) 벽으로 가려고 할 경우 return

line 14) 격자의 범위를 벗어날 경우 return

line 16) 도착지점에 도달할 경우 cnt++

line 20~27) 

line 20, 지나온 길을 1로 치환하여 탐색 방향이 겹치지 않도록 함

line 22~25, 상, 하, 좌, 우 로 이동하는 재귀 함수 호출

line 27, 앞 길을 다 탐색했다면 다시 0으로 치환하여 다른 경우의 수에 반영이 되지 않도록 함

#. Other code

#include<stdio.h>
 
int map[10][10], ch[10][10];
int dx[4]={1, 0, -1, 0};
int dy[4]={0, 1, 0, -1};
int cnt=0;
 
void DFS(int x, int y){    
    int xx, yy, i;
    if(x==7 && y==7){
        cnt++;
    }
    else{
        for(i=0; i<4; i++){
            xx=x+dx[i];
            yy=y+dy[i];
            if(xx<1 || xx>7 || yy<1 || yy>7)
                continue;
            if(map[xx][yy]==0 && ch[xx][yy]==0){
                ch[xx][yy]=1;
                DFS(xx, yy);
                ch[xx][yy]=0;
            }        
        }
    }
}
 
int main(){
    freopen("input.txt", "r", stdin);
    int i, j;
    for(i=1; i<=7; i++){
        for(j=1; j<=7; j++){
            scanf("%d", &map[i][j]);
        }
    }
    ch[1][1]=1;
    DFS(1, 1);
    printf("%d\n", cnt);
    return 0;
}

강사님은 이동경로를 저장하는 배열을 따로 사용하셨고, dx, dy 배열(앞으로 갈 방향)을 사용하셔서 더 코드를 간결하게 짜셨다.

그리고 내 코드는 함수에 들어왔을 때, 격자를 벗어난 유무와 길의 상태를 확인했는데, 위 코드는 함수에 넣기 전에 확인하여

재귀함수의 깊이를 줄일 수 있던 것 같다.

line 10~25) DFS 함수에서 도착지점에 도달했을 경우와, 그렇지 않을 경우, 두 경우로 나누었고

line 11) 마찬가지로 (7, 7) 에 도착했을 때 cnt++ 를 해주었다.

line 14 부터는 for문을 돌면서 앞으로 갈 방향을 정하여 재귀함수를 호출하는데 ,

line 15~16 에서 앞으로 갈 격자의 좌표를 먼저 저장하고

line 17) 앞으로 갈 좌표가 격자를 벗어날 경우 continue

line 19) 앞으로 갈 좌표가 길에 맞고, 왔던 길이 아닐 경우

line 20~22) ch 배열에 체크하고 해당 좌표를 담아서 재귀함수를 호출한다. 

              재귀함수가 끝나면 ch 배열에 체크를 해제하고 다음 방향을 탐색한다.

전체적인 로직을 강사님과 유사하게 잘 구현한 것 같다. Yeahhhhhhhhhh~~!

#. Result

  - Input --------------------------------------------------------

0 0 0 0 0 0 0 

0 1 1 1 1 1 0 

0 0 0 1 0 0 0 

1 1 0 1 0 1 1 

1 1 0 0 0 0 1 

1 1 0 1 1 0 0

1 0 0 0 0 0 0

------------------------------------------------------------------

  - Output --------------------------------------------------------

8

------------------------------------------------------------------