항해 30일차 TIL
1. 억께이 고
이리저리 흔들리면서도 사실 나는 지금 내가 뭘 해야하는지 알고 있다는게 문제였다. 근데 나 혼자서는 그걸 깨닫지 못하고 있다가 어제 매니저님이 다녀가시면서 그제서야 깨달았다... 그리고 누군가가 나 대신 이래라저래라 정리해주고 내 입장도 대변해줬으면 하는걸 내심 은근히 바라고 있었다는것도 깨달았다; 자기의 일은 스스로 하자...
그리고 강단 갖도록 해야지! 나는 내가 좋아하는 사람들에게는 안된다는 말을 못하는 편이다. 기저엔 아마 미움받고 싶지 않다는 심리가 깔려있던 것 같다. 진짜 내 인연이라면 내가 무리해서 노력하지 않아도 내것이 될텐데. 내가 안절부절하며 맞추려고 하지 않아도 함께 갈 수 있는 사람이 진짜 내 인연이겠지. 그리고 어떻게 마음이 항상 쌍방이겠어! 그냥 편하게 그러려니 하자.
덜 휘둘렸더라면 더 많은걸 가져갔을테지만... 이미 지난거 계속 곱씹지 말고 그 시간에 내가 벌려놓은 일들이나 어쨌든 수습해야겠다.
2. 그리움에 사무치는 생물
이든카페 사장님이 보고싶다! 맥북도 샀겠다, 알고리즘 주차만 끝나면 이든카페에 갈거야! 가서 좋아한다고 고백하겠어! (플래그 세우기)
진짜 사장님의 사려깊으면서도 밝은 그 분위기가 진짜 그립다. 내가 이 동네를 떠나지 못하는 이유...
B마담도 보고싶고. 카페 단골들 다 그립다. 생각난 김에 오늘 나가고 싶지만..! 오늘은 아직 플로이드를 이해 못했으니까 포기해야지. 목요일엔 꼭 갈거야.
그리고 우리 천꾸화 스터디도...! 요즘 제대로 참여 못하고 있지만 다들 잘 지내시길 바라며...
3. 플로이드 워셜
일단 강의에서 제공해주신 코드 주석달며 이해해보기
def floyd_warshall(graph):
N = len(graph)
# 계산 편의를 위해 1씩 더했다
dist = [[INF] * (N + 1) for _ in range(N + 1)]
# dist에 값이 전부 INF인 5x5 크기의 그래프가 담긴다.
# dist = [INF, INF, INF, INF, INF], [INF, INF, INF, INF, INF] .. < 5개
for idx in range(1, N + 1):
dist[idx][idx] = 0
# idx가 1일 때 dist[1][1], 2일 때 dist[2][2] ... 돌며
# [1][1], [2][2], [3][3], [4][4]는 0으로 채워준다.
# 제자리에서 시작해 제자리에서 끝나면 이동한 거리가 없기 때문.
for start, adjs in graph.items():
for adj, d in adjs:
dist[start][adj] = d
# items() 함수를 이용해 키, 값 쌍을 돌며 그래프를 마저 채운다
# start = 1, adjs = [(2,4), (4,6)] 일때
# adj = 2, d = 4 -> dist[start][adj] = d 즉 dist[1][2] = 4
# adj = 4, d = 6 -> dist[1][4] = 6 이 된다.
# 이걸 그래프에 전부 채우면 (0 라인 제외하고 1번째부터)
# [0, 4, INF, 6]
# [3, 0, 7, INF]
# [5, INF, 0, 4]
# [INF, INF, 2, 0] 이 된다.
for k in range(1, N + 1):
for a in range(1, N + 1):
for b in range(1, N + 1):
dist[a][b] = min(dist[a][b], dist[a][k] + dist[k][b])
# k가 1, a도 1일 때는 본래 그래프와 같다
# k가 1, a는 2일 때는
# dist[a][b]= 3 , dist[a][k] + dist[k][b]= 3 -> min = 3
# dist[a][b]= 0 , dist[a][k] + dist[k][b]= 7 -> min = 0
# dist[a][b]= 7 , dist[a][k] + dist[k][b]= INF+3 -> min = 7
# dist[a][b]= INF , dist[a][k] + dist[k][b]= 9 -> min = 9
# 이런 과정을 거쳐 k==1일동안 a를 1부터 4까지 전부 돌고 나면
# [0, 4, INF, 6]
# [3, 0, 7, 9]
# [5, 9, 0, 4]
# [INF, INF, 2, 0] 이 된다.
# 계속해서 k가 2일동안 for문을 전부 돌고 나면
# [0, 4, 11, 6]
# [3, 0, 7, 9] -> k=2, a=2인 라인. dist[a][b]와 dist[a][k]+dist[k][b] 값이 같다
# [5, 9, 0, 4]
# [INF, INF, 2, 0]
# k가 3일동안 돌고 나면
# [0, 4, 11, 6]
# [3, 0, 7, 9]
# [5, 9, 0, 4] -> k=3, a=3인 라인. dist[a][b]와 dist[a][k]+dist[k][b] 값이 같다
# [7, 11, 2, 0]
# 마지막으로 k가 4를 마저 돌고 나면
# [0, 4, 8, 6]
# [3, 0, 7, 9]
# [5, 9, 0, 4]
# [7, 11, 2, 0] -> k=4, a=4인 라인. dist[a][b]와 dist[a][k]+dist[k][b] 값이 같다
return dist
N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
graph = defaultdict(list)
for _ in range(M):
a, b, c = map(int, input().split())
graph[a].append((b, c))
# 4
# 7
# 1 2 4
# 1 4 6
# 2 1 3
# 2 3 7
# 3 1 5
# 3 4 4
# 4 3 2
그리고 이건 백준의 플로이드 문제 내가 풀어본 것...
import sys
from collections import defaultdict
INF = int(1e9)
def floyd(graph):
dist = [[INF] * (N) for _ in range(N)]
for i in range(N):
dist[i][i] = 0
for start, adjs in graph.items():
for adj, d in adjs:
dist[start-1][adj-1] = d
for k in range(N):
for a in range(N):
for b in range(N):
dist[a][b] = min(dist[a][b], dist[a][k]+dist[k][b])
return (dist)
graph = defaultdict(list)
for _ in range(M):
a, b, c = map(int, input().split())
graph[a].append((b, c))
floyd(graph)인데. 이건 틀렸다고 한다... 대체 왜? 결국 왜 틀린건지 못 찾고 튜터님의 풀이를 봤다...
import sys
N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
dist = [[INF] * (N) for _ in range(N)]
for i in range(N):
dist[i][i] = 0
for j in range(M):
a, b, c = map(int, input().split())
if c < dist[a-1][b-1]:
dist[a-1][b-1] = c
for k in range(N):
for a in range(N):
for b in range(N):
dist[a][b] = min(dist[a][b], dist[a][k]+dist[k][b])
for row in dist:
print(' '.join([str(el) if el != INF else '0' for el in row]))음! 열심히 해석해봐야지. 근데 이건 제출하니까 타임아웃이 난다...
요즘은 코딩보다 인간되기를 더 배우는 것 같은 느낌