[CLASS 3]백준 11403번 - 경로 찾기

11403번 : 경로 찾기

 

처음에는 약간 재귀의 냄새(?)가 났는데 하다보니 결국 bfs로 풀게 되었다. bfs로 풀면 장점은 속도가 좀 빠르다는 것이고 단점은 구현이 약간 더 어렵다.

 

내 코드(BFS):

# dawitblog.tistory.com
from sys import stdin
from collections import deque
input = stdin.readline

n = int(input())
# 입력받은 행렬
mat = [list(map(int,input().split())) for _ in range(n)]
# 출력할 행렬
mat2 = []

# 각 정점마다 수행
for i in range(n):
    temp = mat[i].copy()
    visited = [False] * n
    queue = deque([j for j in range(n) if mat[i][j]])
    for k in queue:
        visited[k] = True

    # bfs
    while queue:
        t = queue.popleft()
        for k in range(n):
            if mat[t][k] and not visited[k]:
                temp[k] = 1
                visited[k] = True
                queue.append(k)

    mat2.append(temp)

# 출력
print('\n'.join(' '.join(map(str,mat2[i])) for i in range(n)))

 

리스트에 각 정점이 방문할 수 있는 정점의 정보를 저장한 뒤, 언제나 하던듯이 bfs를 작성해 주면 된다.

 

내 코드(플로이드-와샬):

# dawitblog.tistory.com
from sys import stdin
input = stdin.readline

n = int(input())
# 입력받은 행렬
mat = [list(map(int,input().split())) for _ in range(n)]

# 플로이드-와샬
for k in range(n):
    for a in range(n):
        for b in range(n):
            if mat[a][k] and mat[k][b]:
                mat[a][b] = 1

print('\n'.join(' '.join(map(str,mat[i])) for i in range(n)))

 

플로이드-와샬 알고리즘을 사용한다면 훨씬 쉽게 풀 수 있다. 그냥 3중 for문에 집어넣으면 된다.

 

간략하게 설명하자면 정점 a에서 정점 b로 갈 때, 정점 k를 거쳐갈 수 있는지 확인하는 코드이다. if문에서 a->k 가 가능하고 k->b 도 가능한지 확인한 뒤, 둘 다 가능하다면 a->b도 가능하다고 판단하는 것이다. 이를 모든 a, k, b에 대해 돌리면 된다. 대신 bfs에 비해 시간은 조금 더 오래걸린다.