64. 경로 탐색(DFS)

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

문제

코드

//64. 경로 탐색(DFS)
#include <stdio.h>
int n, cnt = 0;
int map[20][20],visited[20];

void DFS(int vertex) {
    if (vertex == n - 1) {
        ++cnt;
    }
    else {
        //i는 다음에 방문할 정점을 의미
        for (int i = 0; i < n; ++i) {
            //방문 가능한 정점(간선 연결)이고 아직 방문하지 않은 정점 조건 확인
            if (visited[i] == 0 && map[vertex][i] == 1) {
                visited[i] = 1;
                DFS(i);
                //리턴되어 돌아온 후 다시 최근 방문했던 정점에 대해 방문체크를 풀어 주어야 다시 다른 정점에서 방문가능하기 때문에 풀어줌
                visited[i] = 0;
            }
        }
    }
}

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

    int m, x, y;
    scanf("%d%d", &n, &m);

    //방향 그래프
    for (int i = 0; i < m; ++i) {
        scanf("%d%d", &y, &x);
        map[y-1][x-1] = 1;
    }

    visited[0] = 1;
    DFS(0);

    printf("%d\n", cnt);

    return 0;
}

문제해결방법

• 정점과 정점과 간선 정보를 입력 받는다.
• DFS로 정점을 매개변수로 넘겨주면 현재 정점에서 갈 수 있는 정점을 확인한 후 방문 표시를 하고 다음 정점으로 넘어간다.
• 마지막 정점 까지 도달 하면 ++cnt 값을 증가시키고 return 하고 다시 호출된 지점으로 돌아가는데 이때 방문체크를 풀어주어야 다시 다른 곳에서 정점을 방문할 때 방문가능 조건이 가능하다.