알고리즘/백준[baekjoon]
[baekjoon] 백준 11403번 : 경로 찾기 (by python) 플로이드-워셜
코딩하는이씨
2022. 7. 19. 21:54
728x90
반응형
https://www.acmicpc.net/problem/11403
11403번: 경로 찾기
가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.
www.acmicpc.net
정답 code
#경로 찾기
n = int(input())
graph = []
for i in range(n):
graph.append(list(map(int,input().split())))
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 i in graph:
for j in i:
print(j, end =' ')
print()
solution
처음엔 문제가 잘 읽히지 않았는데 결론은 간단하다.
문제 예시 처럼 (0,1)가 1이라면 0에서 1로가는 간선이 존재한다는 것이다.
따라서 1에서 0으로가는 간선도 당연히 존재한다.
플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)을 사용하여 해결할 수 있다.
알고리즘에 대한 설명은 아래에 있다.
참고
i에서 j를 가는 간선이 존재한다는건 j에서 i도 가능하다는 것이다.
또한 핵심은 i에서 k에 간선이 존재하고 k에서 j에도 존재하면, i에서 j에 간선이 존재 한다는것이다.
플로이드 - 워셜 알고리즘이 아닌 bfs나 dfs를이용해도 된다.
728x90
반응형