[백준] 11403번 - 경로 찾기 문제 풀이 및 코드 해석 (Python)

1. 문제 분석

📌 문제 개요

• 가중치 없는 방향 그래프 G가 주어질 때, 모든 정점 (i, j)에 대해 경로가 있는지 확인해야 한다.
• i에서 j로 이동 가능한 경우 1, 불가능한 경우 0을 출력해야 한다.
• 입력으로 주어지는 인접 행렬을 기반으로 탐색을 진행한다.

🎯 요구사항

1. i에서 j로 가는 경로가 있는지 확인해야 한다.
2. 모든 정점 쌍 (i, j)에 대해 확인해야 한다.
3. 인접 행렬 형식으로 출력해야 한다.

---

2. 해결 방법

🔹 핵심 개념

• 모든 정점 쌍 (i, j)에 대해 경로를 확인하는 문제 → 플로이드-워셜(Floyd-Warshall) 알고리즘 활용!
• 플로이드-워셜 알고리즘은 모든 노드 간 최단 경로를 구하는 알고리즘으로, O(N^3)의 시간 복잡도를 가진다.
• N ≤ 100이므로 최대 연산 횟수 10^6 → 충분히 해결 가능!

🔑 해결 절차

1. 인접 행렬을 입력받아 graph 배열 초기화
2. 플로이드-워셜 알고리즘 수행
   • k(경유점)를 기준으로 i -> k 경로와 k -> j 경로가 있다면 i -> j도 연결됨
3. 최종 결과 출력

---

3. 코드 구현 (Python)

import sys

input = sys.stdin.readline

N = int(input().strip())
graph = [list(map(int, input().split())) for _ in range(N)]

# 플로이드-워셜 알고리즘 수행
for k in range(N):  # 경유점
    for i in range(N):  # 시작점
        for j in range(N):  # 도착점
            if graph[i][k] == 1 and graph[k][j] == 1:
                graph[i][j] = 1

# 결과 출력
for row in graph:
    print(*row)

---

4. 코드 분석

🔹 주요 알고리즘

1. 플로이드-워셜 알고리즘 활용

   • k를 경유점으로 설정하여 i -> j로 갈 수 있는지 여부를 갱신
   • graph[i][j]는 i -> j로 가는 경로가 있으면 1, 없으면 0

2. 경로 갱신 방식

   • if graph[i][k] == 1 and graph[k][j] == 1:
     • 즉, i에서 k로 가는 길이 있고, k에서 j로 가는 길이 있으면 i -> j도 가능

3. 인접 행렬 형식으로 출력

   • print(*row)를 이용하여 공백을 두고 한 줄씩 출력

---

5. 시간 복잡도 분석

• 플로이드-워셜 알고리즘의 시간 복잡도 → O(N^3)
• 최대 입력 크기 (N = 100)
  • 100^3 = 1,000,000 → 충분히 해결 가능

---

6. 개선할 점 및 대체 방법

✅ 개선할 점

1. BFS/DFS를 활용한 탐색 가능
   • 한 정점에서 다른 정점으로 이동 가능한지를 확인하는 문제이므로
     각 정점마다 BFS/DFS 탐색을 수행하여 O(N^2)에 해결 가능

🔄 대체 방법

1. DFS를 이용한 풀이 (O(N^2))

import sys

input = sys.stdin.readline

N = int(input().strip())
graph = [list(map(int, input().split())) for _ in range(N)]

def dfs(start, node, visited):
    for next in range(N):
        if graph[node][next] == 1 and not visited[next]:
            visited[next] = True
            dfs(start, next, visited)

# DFS를 이용해 경로 갱신
for i in range(N):
    visited = [False] * N
    dfs(i, i, visited)
    graph[i] = [1 if visited[j] else 0 for j in range(N)]

# 결과 출력
for row in graph:
    print(*row)

✔ DFS를 활용하면 O(N^2)로 해결 가능하여 더 효율적일 수 있음