[TIL] 99Club - Baekjoon - [Silver I] 경로 찾기 - 11403
성능 요약
메모리: 31120 KB, 시간: 184 ms
분류
플로이드–워셜, 그래프 이론, 그래프 탐색, 최단 경로
문제 설명
가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.
출력
총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 길이가 양수인 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.
00. 발상
-
우선, 그래프가 인접 행렬 형태로 주어졌고, 예제 출력을 보고 이 2차원 배열 자체를 수정해야한다는 점에서 'Floyd-Warshall' 알고리즘을 먼저 떠올렸다.
[ 최단 거리 알고리즘 (Dijkstra, Bellman-Ford, Floyd Warshall) ] -
Floyd-Warshall 알고리즘에서 경유지 k를 기준으로 하는 3중 for문 형식을 큰 틀로 하여 작성하되, 현재 문제에서는 '경로의 유무'만 판단하면 된다는 점을 중요 문제로 삼았다.
-
이후, 다음의 두 가지 경우로 나누어 발상하였다.
-
(출발지 정점) → (목적지 정점)으로 바로 갈 수 있는 경로가 있는 경우. -
(출발지 정점) → (경유지 정점) → (목적지 정점)으로 갈 수 있는 경로가 있는 경우.
-
01. 코드 작성
- 최종적으로 작성한 코드는 다음과 같다.
# 빠른 입력을 위해 stdin사용
import sys
input = sys.stdin.readline
# 정점 개수 N
N = int(input())
# 그래프 입력
G = [list(map(int,input().split())) for _ in range(N)]
# 거쳐갈 노드 k에 대해
for k in range(N):
# 세로축, 가로축을 기준으로 반복하면서
for i in range(N):
for j in range(N):
# 바로 갈 수 있거나, k를 거쳐 갈 수 있는 노드에 대해
if G[i][j]>0 or G[i][k]>0 and G[k][j] > 0:
# 그래프 배열에 기록
G[i][j] = 1
# 결과 출력
for i in range(N):
print(' '.join(map(str,G[i])))02. 고민했던 부분과 문제 해결
01. 3중 for문 안에서의 조건 분기
- 처음에는 아래와 같이 코드를 작성 했었다.
아래 3중 for문 안에서 if 조건 분기 부분이 다르다.
# 거쳐갈 노드 k에 대해
for k in range(N):
# 세로축, 가로축을 기준으로 반복하면서
for i in range(N):
for j in range(N):
# 바로 갈 수 있거나, k를 거쳐 갈 수 있는 노드에 대해
if G[i][j]>0 or (G[i][k] + G[k][j]) > 0:
# 그래프 배열에 기록
G[i][j] = 1-
하지만, 위와 같은 조건 분기로는 예제 입력에 대해서 올바른 출력이 나오지 않았는데, 생각해보면 다음과 같은 문제가 있다.
-
(G[i][k] + G[k][j]) > 0이라는 조건이 뜻하는 바는 (노드i) → (노드k) → (노드j) 의 경로를 의미하는 것인데, 다음과 같은 예를 들어보자.(노드i) → (노드k) 까지의 간선이 양수이고,
(노드k) → (노드j) 까지의 간선이 0인 경우.
또는
(노드i) → (노드k) 까지의 간선이 0이고,
(노드k) → (노드j) 까지의 간선이 양수인 경우. -
위에서 작성한 코드의 조건 분기로는 이러한 경우를 걸러주지 못한다.
따라서,G[i][k] > 0인 경우와G[k][j] > 0인 경우를 따로 생각 해 주어야 한다. 이러한 발상에서 다음과 같이 코드를 수정할 수 있었다.
# 거쳐갈 노드 k에 대해
for k in range(N):
# 세로축, 가로축을 기준으로 반복하면서
for i in range(N):
for j in range(N):
# 바로 갈 수 있거나, k를 거쳐 갈 수 있는 노드에 대해
if G[i][j]>0 or G[i][k]>0 and G[k][j] > 0:
# 그래프 배열에 기록
G[i][j] = 102. Floyd-Warshall 알고리즘의 연산은 인접 행렬을 갱신하며 일어난다.
-
처음에는 단순한 생각으로
answer라는 리스트를 하나 더 두었었다.
answer = [[0]*N for _ in range(N)]과 같이 말이다. -
하지만, Floyd-Warshall은 반복문 안에서 계속해서 값들을 갱신해가는 알고리즘이기 때문에, 이는 불필요 했다. 오히려 메모리 공간만 더 차지할 뿐이다.
03. 처음에는 예제 입력2, 예제 출력2에서 G[0][0]이 1인 것을 이해하지 못했다.
- (노드0)에 대해 다른 노드를 거쳐 (노드0)으로 돌아올 수 있으면 값이 1이 되는 것이다.
04. 결과 출력에서 join() 연산 사용
- 처음에는 아래와 같은 코드로 결과를 출력했다.
# 결과 출력
for i in range(N):
for j in range(N):
print(G[i][j],end=' ')
print()- 아래와 같이 2차원 배열 반복 안에서
.join()연산을 사용해주면 더 짧은 코드로 작성할 수 있다.
# 결과 출력
for i in range(N):
print(' '.join(map(str,G[i])))03. 회고 및 느낀 점
-
또 새로운 도전이 시작 되었다. '1일 1코테'라는 것이 말이 쉽지, 여태 혼자 목표로 하고 있었을 때는 어느 정도 막연하고 가끔 한 번씩 건너뛸 때도 있었다.
-
타이머가 시각적으로 보여지고, 그 날 어떤 문제를 풀 지 고민하지 않아도 되다보니 99 클럽의 효과가 첫 날부터 느껴졌다.
-
오늘 문제는 개인적으로 중간에 연결되는 발상만 조금 더 빠르게 할 수 있었다면 시간을 단축할 수 있지 않았을까 싶다.
-
정글 과정을 수행하면서, 또 일을 벌렸다. 점점 과거의 내가 벌려놓은 일을 수습하는 오늘의 내가 힘들어지고 있다.
이 또한 계속 반복하다보면 당연하게 할 수 있는 날이 오겠지.
앞으로 열심히 해보자.
#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL
