65. 미로탐색(DFS)

it 취업을 위한 알고리즘 문제풀이

문제

코드

#include <stdio.h>

int map[7][7], visited[7][7];
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
int cnt;

void go(int y, int x) {
    if (y == 6 && x == 6) {
        ++cnt;
    }
    else {
        for (int i = 0; i < 4; ++i) {
            // xx, yy는 다음에 갈 곳, x,y는 현재 위치
            int xx = x + dx[i];
            int yy = y + dy[i];

            if (xx >= 0 && xx < 7 && yy >= 0 && yy < 7 && map[yy][xx] == 0 && visited[yy][xx] == 0) { 
                visited[yy][xx] = 1;
                go(yy, xx);
                //직전에 방문 한곳 다시 미방문 처리
                visited[yy][xx] = 0;
            }
        }
    }
}

int main() {
    freopen("input.txt", "rt", stdin);

    for (int i = 0; i < 7; ++i) {
        for (int j = 0; j < 7; ++j) {
            scanf("%d", &map[i][j]);
        }
    }

    visited[0][0] = 1;
    go(0, 0);

    printf("%d", cnt);
    return 0;
}

문제해결방법

• DFS 알고리즘으로 완전탐색 수행했다.
  • for 문으로 i값 마다 dx[], dy[]를 통해 상하좌우 방향을 설정하고 현재 위치 x,y에서 dx[],dy[]의 값을 더해주어 문제의 조건에서 벗어나지 않는 위치 인지 확인하고(배열의 범위에서 벗어나지 않고, 벽이 아닌곳) 방쿤체크를 한후 다음 뎁스로 진행한다.
  • 마지막 뎁스 까지 진행 하면 카운트 값을 증가시켜준다.
  • 다시 함수를 호출한 원래 위치로 돌아오면 방금 전 방문한 곳은 미방문처리로 바꿔주어 다시 다른방향을 통해 갈 수 있도록 해준다.