99클럽 코테 스터디 1일차 TIL, Floyd-Warshall

항해99의 코테스터디에 참여 하게 되었다. 원래는 C++로 PS를하지만 PCCP Python 자격증을 따고싶어 Python으로 할 예정이다. 최근에 코테를 봤을 때도 문자열 파싱하는 문제가 좀 나왔었는데 파이썬으로 하면 쉬울텐데 함수가 기억나지 않아 시간을 오히려 많이 쓸 것 같아 직접 구현하며 시간을 소모했던 점도 크게 다가왔다. 앞으로 더 유리한 언어를 쓰며 PS를 할 수 있도록... 그리고 PCCP 만점을 위해...

• 문제: Baekjoon 11403: 경로찾기
• 설명: 인접행렬이 주어졌을 때 각 노드에서 갈 수 있는 모든 노드들을 출력하라
  • 각 노드 쌍들이 서로 연결되어있는지를 묻는 문제이다.
• Floyd-Warshall Algorithm
  • 모든 노드 쌍의 최단 거리를 구할 수 있는 알고리즘으로써 DP 기반으로 이루어진다.
  • 기본 개념은 노드 $A$에서 노드 $B$로 가는 최단 경로가 $a$이고 노드 $B$에서 노드 $C$로 가는 최단 경로가 $b$일 때
  • 노드 $A$에서 노드 $C$로 가는 최단 경로는 $a + b$이다.
  • 위의 개념을 모든 쌍에 대해서 구해주면 된다.
• 문제 풀이
  • 위의 개념을 진짜 사알짝 응용하면
    • 노드 $A$에서 노드 $B$가는 경로가 있고 노드 $B$에서 노드 $C$로 가는 경로가 있으면 노드 $A$에서 노드 $C$로 가는 경로도 존재한다.
  • 그대로 구현하자

Code

# Baekjoon11403.py
import sys, copy
input = sys.stdin.readline

n = int(input())
adjMat = [list(map(int, input().split())) for _ in range(n)]

ans = copy.deepcopy(adjMat)
for k in range(n):
    for i in range(n):
        for j in range(n):
            if (ans[i][k] and ans[k][j]): # i -> k로 가는 경로가 있고 k ->j로 가는 경로가 있으면 i->j로 가는 경로가 있다.
                ans[i][j] = 1

for a in ans:
    for b in a:
        print(b, end=' ')
    print()

지금 생각해보면 deepcopy를 굳이 안쓰고 바로 adjMat에 추가해도 되었을듯하다. 추가적으로 다른 분들 코드를 보다 생각난건데 리스트 출력할 때 print(*a)로 하면 리스트가 분해되서 출력된다. 다음부터 써야겠다.