[백준] 경로 찾기 (DFS, 플로이드-와샬)

이번에는 경로 찾기 기본 문제에서 아주 약간 변형된 문제에 대해서 알아보자.

 

백준 11403번 경로 찾기

아주 간단한 문제지만 그놈의 고정 관념 때문에 푸는데 상당히 많은 시간이 소요되었다. 이 문제는 BFS, DFS, 플로이드-와샬 알고리즘으로 풀 수 있으며, 재귀 함수 연습(?)을 위해 DFS로 풀었다.

 

입력 값은 아래와 같다.

7
0 0 0 1 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 0 1 1 0
1 0 0 0 0 0 0
0 0 0 0 0 0 1
0 0 1 0 0 0 0

 

코드는 아래와 같다.

 

#include <stdio.h>
#define MAX 101

int map[MAX][MAX];
int result[MAX][MAX];
int visited[MAX];

void DFS (int start, int limit) {
	// 시작점에서 이동 가능한 모든 정점 탐색
	for (int v = 0; v < limit; v++) {
		// 방문하지 않았고, 이동 가능하면 DFS 시작
		if (!visited[v] && map[start][v]) {
			// 방문 표시는 나중에. 순회가 있을 수 있으므로
			visited[v] = 1;
			
			// DFS 재귀 호출
			DFS(v, limit);
		}
	}
}

int main(void) {
	int N = 0;
	
	scanf("%d", &N);
	
	for (int start = 0; start < N; start++) {
		for (int end = 0; end < N; end++) {
			scanf("%d", &map[start][end]);
		}
	}
	
	// 맵 탐색 시작
	for (int s = 0; s < N; s++) {
		DFS(s, N);
		
		for (int v = 0; v < N; v++) {
			result[s][v] = visited[v];
		}
		
		for (int i = 0; i < N; i++) {
			visited[i] = 0;
		}
	}
	
	// 결과 출력
	for (int start = 0; start < N; start++) {
		for (int end = 0; end < N; end++) {
			printf("%d ", result[start][end]);
		}
		printf("\n");
	}
	
	return 0;
}

이 문제에 한가지 함정이 있는데, 예를 들어 3개의 정점 0, 1, 2가 있고 0 > 1 > 2 > 0 으로 간선이 연결되어 있다고 가정하자. 정점 2에서 0으로 이동 가능하기 때문에 사이클이 있는 방향 그래프라고 볼 수 있다.

 

만약에 정점 1에서 정점 0으로 이동 가능한 간선이 있는지 물어봤다면 당연히 No 라는 결과를 출력하겠지만, 이 문제에서 물어보는 것은 경로임에 주의하자. 즉, 단방향 그래프라도 정점 1에서 0까지 이동 가능한 경로는 1 > 2 > 0으로 이동 가능한 경로가 존재한다.

 

위의 예시와 같이 싸이클이 존재하는 경우, 단방향 그래프에서 인접 정점이 아니더라도 이동 가능한 경로가 나올 수 있기 때문에 모든 정점을 시작 정점으로 지정하고 끝가지 따라가봐야 한다. 이 때, 방문 표시를 초기화 하지 않으면 다른 정점들에 대한 경로를 찾을 수 없으므로 DFS가 모두 끝나면 방문 정보를 초기화 해야한다.

for (int s = 0; s < N; s++) {
  DFS(s, N);

  for (int v = 0; v < N; v++) {
  	result[s][v] = visited[v];
  }

  for (int i = 0; i < N; i++) {
  	visited[i] = 0;
  }
}

 

이 문제는 플로이드-와샬 알고리즘으로도 풀 수 있는데, 플로이드-와샬 알고리즘이란 모든 정점에 대한 최단 경로를 찾을 때 사용하는 알고리즘이기 때문이다. 기본적인 플로이드-와샬 알고리즘의 구조는 아래와 같다.

for (경유지) {
	for (출발지) {
    	for (목적지) {
        	가중치가 있으면 간선완화 진행
        }
    }
}

 

이 문제를 플로이드-와샬로 풀면 아래와 같다.

/******************************************************************************

Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, Java, PHP, Ruby, Perl,
C#, VB, Swift, Pascal, Fortran, Haskell, Objective-C, Assembly, HTML, CSS, JS, SQLite, Prolog.
Code, Compile, Run and Debug online from anywhere in world.

*******************************************************************************/
#include <stdio.h>
#define MAX 101
#define INFI 9999

int G[MAX][MAX];

int main()
{
    int N = 0;
    
    scanf("%d", &N);
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &G[i][j]);
            getchar();
        }
    }
    
    // 정점 i에서 정점 j로 가는 경로 체크
    for (int k = 0; k < N; k++) {
    	for (int i = 0; i < N; i++) {
    		for (int j = 0; j < N; j++) {
    			if (G[i][k] && G[k][j]) {
    				G[i][j] = 1;
    			}
    		}
    	}
    }
    
    // 출력
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%d ", G[i][j]);
        }
        printf("\n");
    }
    
    return 0;
}

플로이드-와샬 알고리즘은 3개의 중첩 반복문으로 구성되며, 경유지 > 출발지 > 목적지 순으로 반복문을 중첩한다. 플로이드-와샬로 이 문제를 풀기 위해서는 출발지 > 경유지 && 경유지 > 도착지 모두 이동이 가능 한지만 체크하면 된다.