[백준/DFS-BFS] 11403: 경로 찾기 - 파이썬

문제

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

11403번: 경로 찾기

 

풀이

3가지 풀이 방법으로 풀었다. BFS 풀이방법이 실행시간이 제일 짧았으며 그 다음은 DFS, 마지막으로 플로이드-와샬 알고리즘을 사용한 방법이 제일 느렸다.

 

먼저 BFS로 푼 방법이다. 

각 정점마다 방문했는지 visited에 저장하고 간선으로 해당 정점이 연결되어 있다면 check에 1을 기록하였다. 

이때 visited는 각 정점을 방문하면서 방문했는지 기록해야 한다. 

# BFS
from collections import deque

n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[0]*n for _ in range(n)]

def bfs(x):
    queue = deque()
    queue.append(x)
    check = [0 for _ in range(n)]

    while queue:
        q = queue.popleft()

        for i in range(n):
            if check[i] == 0 and graph[q][i] == 1:
                queue.append(i)
                check[i] = 1
                visited[x][i] = 1

for i in range(0, n):
    bfs(i)

for i in visited:
    print(*i)

 

그 다음은 DFS로 푼 방법이다. 

# DFS
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [0 for _ in range(n)]

def dfs(x):
    for i in range(n):
        if graph[x][i] == 1 and visited[i] == 0:
            visited[i] = 1
            dfs(i)

visited = [0 for _ in range(n)]
for i in range(n):
    dfs(i)
    for j in range(n):
        if visited[j] == 1:
            print(1, end=' ')
        else:
            print(0, end=' ')
    print()
    visited = [0 for _ in range(n)]

 

다음은 플로이드-워셜 알고리즘으로 구한 방법이다. 

# 플로이드-와샬 알고리즘을 이용한 풀이
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]

for i in range(n):
    for j in range(n):
        for k in range(n):
            if graph[j][i] and graph[i][k]:
                graph[j][k] = 1
                
for g in graph:
    print(*g)