[Python] 백준 11403번 경로 찾기

 

https://www.acmicpc.net/problem/11403

11403번: 경로 찾기

| 문제 내용

| 풀이

1. 플로이드 워셜(floyd warshall) 알고리즘 이용

가장 간단하지만 O(n^3)의 시간복잡도를 가진다.

import sys
input = sys.stdin.readline

n = int(input())

graph = []
for i in range(n):
    graph.append(list(map(int, input().split())))

# floyd warshall
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(' '.join(map(str, row)))

2. BFS

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())

graph = []
for i in range(n):
    graph.append(list(map(int, input().split())))
    
# bfs 0부터 시작해서 연결되어있는 점들부터 검사해나감
visited = [[0] * n for _ in range(n)]
def bfs(x):
    queue = deque()
    queue.append(x)
    is_connected = [0 for _ in range(n)] # 정점 n을 기준으로 0 ~ n까지 연결되어있는지 확인

    while queue:
        vertex = queue.popleft()

        for i in range(n):
            if is_connected[i] == 0 and graph[vertex][i] == 1:   # 연결 안 됐지만 연결 가능한 상태인 정점
                is_connected[i] = 1
                visited[x][i] = 1
                queue.append(i)

# 모든 정점을 돌면서 체크
for i in range(n):
    bfs(i)

for row in visited:
    print(' '.join(map(str, row)))

3. DFS

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())

graph = []
for i in range(n):
    graph.append(list(map(int, input().split())))

visited = [[0] * n for _ in range(n)]
def dfs(x):
    stack = []
    stack.append(x)
    is_connected = [0 for _ in range(n)]

    while stack:
        vertex = stack.pop()
        for i in range(n):
            if is_connected[i] == 0 and graph[vertex][i] == 1:
                is_connected[i] = 1
                visited[x][i] = 1
                stack.append(i)

# 모든 정점을 돌면서 체크
for i in range(n):
    dfs(i)

for row in visited:
    print(' '.join(map(str, row)))

| 느낀점

사실 플로이드 워셜말고는 생각이 안났어서 BFS, DFS는 검색해보고 추가하였다. 시간이 중요한 문제였고 N의 범위가 컸다면 아마 틀렸을 것 같아 그래프 탐색 문제를 좀 더 깊게 공부해야겠다는 생각이 들었다.