백준 11403번 '경로 찾기' 알고리즘 설명

✨ Written with ChatGPT

KEY POINT

정점별 DFS를 통한 직·간접 경로 판별

문제 상황

백준 11403번 경로 찾기 문제를 보고 어떻게 접근해야 될지 막막했다.
처음엔 예시 입출력도 이해가 안되었다.

이 문제는 모든 정점에서의 도달 가능성 여부를 확인하는 전형적인 그래프 탐색 문제다.
방향 그래프가 주어졌을 때, 정점 i에서 j로 가는 경로가 존재하는지 출력하는 문제이다.
입력으로 주어지는 인접 행렬은 직접 연결만 나타낸다.
하지만 이 문제는 직접 연결된 것뿐만 아니라 중간에 다른 정점을 거쳐서 도달 가능한지도 확인해야 한다.

각 정점에서 출발해 도달 가능한 모든 정점을 찾고, 그 여부를 행렬 형태로 출력하면 된다.

DFS 설명

시간복잡도 & 공간복잡도

시간복잡도

각 정점에서 DFS: O(N)
각 DFS의 복잡도: O(N²) (모든 간선 확인)
전체: O(N³)

공간 복잡도

인접행렬: O(N²)
결과 행렬: O(N²)
방문 배열: O(N)
전체: O(N²)

장단점

장점

재귀 호출을 통해 구현이 간단하고 직관적
- 한 정점에서 출발해 갈 수 있는 모든 정점을 탐색할 수 있음
메모리 사용량이 적음
희소 그래프에서 효율적 (정점 수가 작을 때(100 이하) 효율적)

단점

조밀한 그래프에서는 느림
재귀 호출로 인한 스택 오버플로우 가능성

이 문제는 최단 거리 계산이 필요 없기 때문에 DFS로 충분하다.

탐색 원리

정점 A에서 시작 → 간선 확인 → 있으면 이동 → 경로 표시

인접행렬 VS. 경로행렬

인접행렬

직접 연결된 간선 정보 표시
연결 有 → 1, 無 → 0으로 표시

경로행렬

직·간접적으로 도달 가능한 모든 경로 정보
경로 有 → 1, 無 → 0으로 표시

제출한 코드

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> graph;
vector<bool> visited;
vector<vector<int>> result;

void dfs(int start, int current) {
	visited[current] = true;

	for (int next = 0; next < graph.size(); next++) {
		if (graph[current][next] == 1) {
			result[start][next] = 1;  // 간선이 있을 때만 경로 표시
			if (!visited[next]) {
				dfs(start, next);
			}
		}
	}
}

int main() {
	int N;
	cin >> N;

	graph.resize(N, vector<int>(N, 0));
	result.resize(N, vector<int>(N, 0));

	// 그래프 입력
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> graph[i][j];
		}
	}

	// 각 정점에서 출발하여 DFS 실행
	for (int i = 0; i < N; i++) {
		visited.assign(N, false);  // 방문 배열 초기화
		// TODO: i번 정점에서 시작하는 DFS 호출
		dfs(i, i);
	}

	// 결과 출력
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout << result[i][j] << " ";
		}
		cout << '\n';
	}

	return 0;
}

성능 비교

방법	시간 복잡도	구현 난이도	특징
DFS	`O(N²)`	쉬움	단순 탐색용으로 적합
플로이드 워셜	`O(N³)`	쉬움	모든 쌍 최단 경로 문제에 적합

이 문제는 단순히 경로 유무만 확인하면 되므로 DFS로 충분하다.
플로이드 워셜은 모든 경우를 전수 조사하는 방식이라 비효율적이다.
노드 개수가 100 이하로 작기 때문에 DFS가 더 빠르게 작동한다.

다르게 풀어보기

5.1 플로이드-워셜 알고리즘

for (int k = 0; k < N; k++) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (graph[i][k] && graph[k][j]) {
                graph[i][j] = 1;
            }
        }
    }
}

장점

더 간단한 구현

단점

O(N³)의 시간복잡도라서 실행 시간 더 오래 걸림

5.2 BFS 활용


void bfs(int start) {
    queue<int> q;
    vector<bool> visited(N, false);
    
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        
        for (int next = 0; next < N; next++) {
            if (graph[current][next] == 1) {
                result[start][next] = 1;
                if (!visited[next]) {
                    visited[next] = true;
                    q.push(next);
                }
            }
        }
    }
}

장점

스택 오버플로우 위험 없음
메모리 사용 패턴이 더 예측 가능

하지만 이 문제는 위와 같은 최적화 없이도 제한 시간 내 충분히 통과된다.

핵심 레슨런

DFS는 도달 가능한 정점을 확인하는 데 매우 효과적인 알고리즘이다.
인접 행렬로 주어진 그래프 문제는 DFS로 풀기 적합하다.
최단 경로 계산이 아니라 경로 존재 여부만 판단하면 되는 문제는 굳이 플로이드-워셜 알고리즘을 안 써도 더 간단하게 접근할 수 있다.

결론

문제의 가장 단순한 해결책을 찾는 연습을 많이 해야겠다.
이 문제는 복잡한 알고리즘보다 기초적인 DFS로 충분히 해결 가능한 문제였고,
모든 정점에 대해 DFS를 한 번씩만 돌려도 정답을 구할 수 있었다.

불필요하게 복잡한 해결 방식보다 문제의 본질을 이해한 뒤 가장 간단한 방법을 선택하는 것이 중요하다는 것을 느꼈다.