[백준 플로이드-와셜 ] 11403 경로 찾기

🥕 [ 백준 11403 ] 경로 찾기

문제 링크

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

11403번: 경로 찾기

 

참고:

https://callmescone.tistory.com/150?category=1097465 

[알고리즘] 최단 경로 플로이드 워셜 알고리즘

 

🍒 문제 분석

인접행렬 그래프가 주어지면, 답안으로는 모든 정점 (i,j) 에 대해, i에서 j로 가는 경로가 있으면 1, 없으면 0을 갖는 인접 행렬로 출력

가령 예제 입력 1에서는 0번 노드 -> 1번 노드 -> 2번 노드 -> 0번 노드 의 경로가 있어 모든 노드에서 모든 노드로 가는 경로가 다 있다.

 

 

🥑 코드

N = int(input())
graph = []

# 그래프를 만들어준다.
for i in range(N):
    graph.append(list(map(int, input().split())))

# 경로 K 가 상위 for문이 된다.
for k in range(N):
    for a in range(N):
        for b in range(N):
            graph[a][b] = max(graph[a][b], graph[a][k]*graph[k][b])

for i in range(N):
    print(' '.join(map(str, graph[i])))

 

🍓 내 해결 과정

처음에는 플로이드 와셜을 미처 공부 안했었기 때문에,  dfs 함수를 만든 후, 각 노드에 대해 dfs 함수를 다 돌리는 식으로 풀었었다. (성공)

그러나 나중에 공부 해보니, 결과적으로 이 풀이가 플로이드 와셜 풀이와 다를 바가 없고 ( 모든 경우를 다 체크 한다는 점에서 ) 플로이드 와셜 풀이가 두 배 더 빨랐다.

 

아래는 처음에 푼 코드

from collections import deque
N = int(input())
graph = [[] for _ in range(N)]
ans_graph = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
    graph[i].extend(list(map(int, input().split())))

def bfs(start):
    visited = [False]*(N)
    q = deque()
    q.append(start)
    while q :
        v = q.popleft()
        visited[v] = True
        if v != start:
            ans_graph[start][v] = 1
        for idx, items in enumerate(graph[v]):
            if items == 1 and idx == start :
                ans_graph[start][start] = 1
            if items == 1 and not visited[idx] :
                q.append(idx)

for i in range(N):
    bfs(i)

for i in range(N):
    print(' '.join(map(str, ans_graph[i])))

 

🍉 깨달은 점 및 정리

1. " 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로 " 라는 말에서 플로이드 와셜 문제라는 것을 알 수 있었다.

 

2. 문맥 상에 1번에 해당하는 내용을 숨겨두기도 한다고 한다. 잘 체크해서 보자.