백준 11403

<경로 찾기>

난이도 : 실버1

1. 백준 문제
   11403

2. 코드 알고리즘

• 플로이드 워셜 알고리즘

11404 의 풀이를 참고

• 11403 풀이

플로이드-워셜 알고리즘을 적용하기 위해 인접리스트를 적절히 수정하는 것이 중요

2-1. 슈도 코드

#11403

정점의 개수 N개
D = []

#N개의 줄 그래프
for i in range(N):
	a = list(map(int, input().split()))
	D.append(a)

for i in range(N):
	for j in range(N):
		노드 값이 0일 경우에 sys.max로 바꾸기
		노드 값이 1인 경우에 0으로 바꾸기

#플로이드-워셜 알고리즘 수행
for 가중치 in  N:
	for 시작노드 in N:
		for 도착노드 in N:
			if D[i][j] > D[i][k] + D[k][j] 
				D[i][j] = D[i][k] + D[k][j] 


# for i in N
	for j in N:
		if D[][] == 0 일경우: (연결됐으므로)1출력하기
		else: 0 출력

3. 코드

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

import sys
input = sys.stdin.readline

N = int(input())
D= []
for i in range(N):
    a = list(map(int, input().split()))
    D.append(a)

#초기화
#노드값이 0(연결돼지 않은 경우)에는 max로 바꾸기
max = sys.maxsize
for i in range(N):
    for j in range(N):
        if D[i][j] == 0:
            D[i][j] = max
        else: #인접리스트 1(연결)은 0으로 바꾸기
            D[i][j] = 0


#플로이드- 워셜 알고리즘 수행
for K in range(N): #k가 가장 먼저 온다는 게 중요_즉, 가중치 우선으로 전개
    for S in range(N):
        for E in range(N):
            #print(K, S, E)
            if D[S][E] > D[S][K] + D[K][E]: #D[x][y]에서 x가 출발노드, y가 도착노드
                D[S][E] = D[S][K] + D[K][E] #K를 경유해서 가는 게 더 짧을 경우 업데이트

#만약 사이클이 없는 독립적인 노드라면 연결되지 않은 노드이므로 1출력되야됨
for i in range(N):
    for j in range(N):
        if D[i][j] == 0:
            print(1, end=" ")
        else:
            print(0, end=" ")
    print("")

4. 코드 후기

• 인접리스트 변형!
  빠르게 해결한 문제!! 플로이드-워셜 알고리즘을 적용하기 위해 입력받은 인접리스트를 변형해야 된다.
  가중치가 없는 그래프이므로 연결된 리스트의 가중치를 1로 하면 문제가 생긴다. 그래서 연결된 노드일경우 가중치를 0으로 설정하고 대신, 연결되지 않은 노드들 끼리는 가중치를 max로 둬 연결되지 않음을 표현한다.

근데 정국이 신곡 seven 실화냐? 미쳤네 플로이드 워셜 알고리즘 작성하려는데 계속 먼데이 튜스데이 웬즈데이 둠칫둠칫 거리는 중...
HE IS KPOP