65. 미로탐색 [DFS]

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅

 

 

입력예제 1

0000000

0111110

0001000

1101011

1100001

1101100

1000000

 

출력예제 1

8

 

풀이 

- 앞서 푼 64번 문제의 격자 형태 변형 문제

- 격자 탐색(상, 하, 좌, 우 탐색) 시 dx, dy 배열을 이용함

- 새로 탐색할 좌표  xx = n+dx[i] , yy= m+dy[i] 이때 상하좌우 4번 탐색하기 때문에 for문은 0~4까지 돌면 된다

- 상하좌우 탐색 시 좌표가 1보다 작아지거나 7보다 커지면 안되기 때문에 continue로 아무 처리 없이 지나가게 한다

- 새로운 좌표인 xx, yy로 탐색하기 전 ch[xx][yy]에 1을 넣은 후 DFS호출 => 이후 ch[xx][yy]을 다시 0으로 초기화

 

#include <stdio.h>
#include <algorithm>
using namespace std;
int map[10][10], ch[10][10], cnt=0;
int dx[4]={-1, 0, 1, 0};
int dy[4]={0, 1, 0, -1};

//65. 미로 탐색(DFS)

void DFS(int n, int m){
    int i, xx, yy; //xx yy는 앞으로 갈 격자
    if(n==7 && m==7){
        cnt++;
    }else{
        for(i=0;i<4;i++){
            xx = n+dx[i];
            yy = m+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(){
    int i, j;
    for(i=1;i<=7;i++){
        for(j=1;j<=7;j++){
            scanf("%d", &map[i][j]);
        }
    }
    ch[1][1]=1; //1,1은 방문
    DFS(1,1);
    printf("%d\n", cnt);
}