[백준] 11403번 경로 찾기 [Python] - DFS, BFS, 플로이드–워셜

 

 

 

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 $(i,j)$에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 문제

플로이드–워셜, dfs, bfs를 사용한 코드들을 작성해봤습니다.

문제

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 $(i,j)$에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N $(1\le N\le 100)$이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.

출력

총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 길이가 양수인 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.

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

 

플로이드–워셜 알고리즘을 사용한 코드 - 1

 

graph를 NxN 크기 2차원 리스트에 저장하고

연결 안 된 곳은 거리를 무한대로 설정해서

i에서 j로 이동하는 경로의 거리를 최솟값으로 업데이트해서

무한대가 아닌 거리라면 이동 가능하므로 1

무한대이면 이동 불가능 하므로 0으로 출력

import sys
INF = float('inf')
N = int(sys.stdin.readline())
graph = [[INF]*N for _ in range(N)]
for i in range(N):
    for j, k in enumerate(sys.stdin.readline().rstrip().split()):
        if k == "1":
            graph[i][j] = 1

for node in range(N):
    for i in range(N):
        for j in range(N):
            graph[i][j] = min(graph[i][j], graph[i][node]+graph[node][j])

answer = [['1']*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if graph[i][j] == INF:
            answer[i][j] = '0'

print("\n".join(" ".join(row) for row in answer))

 

플로이드–워셜 알고리즘을 사용한 코드 -2

 

위 코드에서 무한대로 설정하는 과정 없이

거리가 0인 경우에 $($거리가 1이면 확인할 필요가 없음$)$

node$($다른 지점$)$를 거쳐서 이동 가능하다면 1로 값을 바꿔줬습니다.

import sys
N = int(sys.stdin.readline())
graph = []
for _ in range(N):
    graph.append(sys.stdin.readline().rstrip().split())

for node in range(N):
    for i in range(N):
        for j in range(N):
            if graph[i][j] =='0' and graph[i][node] == graph[node][j] == '1':
                graph[i][j] = '1'

print("\n".join(" ".join(row) for row in graph))

 

dfs를 사용한 코드 - 1

graph를 NxN 크기 2차원 리스트에 저장하는 대신

i에서 j로 가는 길이 연결됐으면 i열에 j를 추가해서

각 열에 연결된 지점의 index를 저장했습니다.

 

방문해서 업데이트 할 NxN 리스트를 생성하고,

dfs를 사용해서 i와 연결된 점 k에 대해

k연결되고, i와 직접적으로는 연결이 안 된 지점을 1로 업데이트 하는 과정을 재귀적으로 반복했습니다.

import sys
def dfs(i, j):
    for k in graph[j]:
        if ans[i][k] == '0':
            ans[i][k] = '1'
            dfs(i, k)

N = int(sys.stdin.readline())
graph = [[] for _ in range(N)]
for i in range(N):
    tmp = sys.stdin.readline().rstrip().split()
    for j, k in enumerate(tmp):
        if k == '1':
            graph[i].append(j)

ans = [['0']*N for _ in range(N)]
for i in range(N): dfs(i, i)

print("\n".join(" ".join(row) for row in ans))

 

bfs를 사용한 코드

위 dfs 코드-1을 조금만 수정해서

방문해서 업데이트 하는 1xN 리스트를 매번 생성하고 dfs를 사용했습니다.

import sys
def bfs(i):
    q = [i]
    while q:
        p = q.pop(0)
        for k in graph[p]:
            if v[k] == '0':
                v[k] = '1'
                q.append(k)

N = int(sys.stdin.readline())
graph = [[] for _ in range(N)]
for i in range(N):
    tmp = sys.stdin.readline().rstrip().split()
    for j, k in enumerate(tmp):
        if k == '1':
            graph[i].append(j)

ans = []
for i in range(N):
    v = ['0']*N
    bfs(i)
    ans.append(" ".join(v))

print("\n".join(ans))

 

dfs를 사용한 코드 - 2

방문해서 업데이트 하는 1xN 리스트를 매번 생성하고 dfs를 사용했습니다.

import sys
def dfs(i):
    for k in graph[i]:
        if v[k] == '0':
            v[k] = '1'
            dfs(k)

N = int(sys.stdin.readline())
graph = [[] for _ in range(N)]
for i in range(N):
    tmp = sys.stdin.readline().rstrip().split()
    for j, k in enumerate(tmp):
        if k == '1':
            graph[i].append(j)

ans = []
for i in range(N):
    v = ['0']*N
    dfs(i)
    ans.append(" ".join(v))

print("\n".join(ans))

 

 

예제 입력 1 

3
0 1 0
0 0 1
1 0 0

예제 출력 1 

1 1 1
1 1 1
1 1 1

예제 입력 2 

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

예제 출력 2 

1 0 1 1 1 1 1
0 0 1 0 0 0 1
0 0 0 0 0 0 0
1 0 1 1 1 1 1
1 0 1 1 1 1 1
0 0 1 0 0 0 1
0 0 1 0 0 0 0