백준 11403번 경로 찾기 :: 마이구미

이번 글은 백준 알고리즘 문제 11403번 "경로 찾기" 를 다뤄본다.

이 문제는 그래프의 DFS, BFS 를 활용하는 문제이다.

DFS, BFS - http://mygumi.tistory.com/102

백준 알고리즘 문제 11403번 경로 찾기 - https://www.acmicpc.net/problem/11403

가중치 없는 방향 그래프 G가 주어졌을 때, 

모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

친절하게 문제에서 어떤 그래프인지 말해주고 있다.

가중치가 없는 방향 그래프라고 명시되어 있다.

그래프에 대한 글에서 무방향 그래프를 기준으로 다뤘었다.

차이는 단지 방향이 있고 없고 차이뿐이다.

// 무방향 그래프 인접행렬
a[v1][v2] = 1;
a[v2][v1] = 1;

// 방향 그래프 인접행렬
a[v1][v2] = 1;

위와 같이 무방향이기에 양방향 모두 간선처리를 해주었고, 방향 그래프인 경우에는 방향대로만 간선처리를 해주면 된다.

그렇기에 인접행렬은 아래와 같이 만들 수 있다.

for (int i = 1; i <= n; i++) {

    for (int j = 1; j <= n; j++) {
        a[i][j] = sc.nextInt();
    }

}

이젠 만들어진 인접행렬을 통해 정점에서 정점까지 경로가 존재하는 지 찾아야한다.

예를 들어보자.

위와 같이 주어진 인접행렬을 통해 정점 간의 간선과 그래프를 표현할 수 있다.

문제에서 원하는 것은 어떤 정점에서 어떤 정점까지의 경로가 존재하는 여부이다.

예를 들어, i가 1이고, j가 5일 경우를 보자.

1->2->4->5 연결된 간선을 통해 경로가 존재한다.

i가 2이고, j가 3일 경우를 보자.

간선은 있지만 무방향 그래프가 아니므로 2에서 3으로 가는 간선이 존재하지 않는다.

i가 3이고, j가 4일 경우를 보자.

3에서 4의 경로를 찾을 때 3과 4는 연결된 간선이 없으므로 경로가 없다라고 생각할 수 있지만, 이 경우 헷갈려서는 안된다.

3->2->4 처럼 탐색이 가능하기 때문이다.

DFS의 특성상 깊이 탐색하기 때문에  각 정점을 기준으로 DFS를 돌면서 방문여부를 체크하면 된다.

즉, DFS는 한 정점을 기준으로 잡고 그 정점에 연결된 정점을 탐색한다. 

방문했다면 기준 정점과 방문 정점간의 연결되었기 때문에 경로가 존재하는 것이 된다.

for (int i = 1; i <= n; i++) {
    dfs(a, c, i);

    for (int j = 1; j <= n; j++) {

        path[i][j] = c[j];

    }
    Arrays.fill(c, 0);
}

이처럼 각 정점이 다른 정점과의 연결관계를 찾을 때에는 BFS보다 DFS를 이용해 쉽게 구현할 수 있다.

전체 소스를 통해 확인하길 바란다.

백준 알고리즘 문제 11403번 전체 소스 Github URL

https://github.com/hotehrud/acmicpc/blob/master/algorithm/graph/11403.java