1) 백준 13549 : 숨바꼭질 3
import heapq
INF = int(1e9)
minlst = [INF]*100001
n,k = map(int,input().split())
def dijkstra(start,end):
minlst[start] = 0
heap = [(0,start)]
while heap:
dist,now = heapq.heappop(heap)
if now == k:
break
elif dist > minlst[now]:
continue
else:
graph = [(now-1,1),(now+1,1),(now*2,0)]
for endPoint,w in graph:
if endPoint >= 0 and endPoint <= 100000 and dist+w < minlst[endPoint]:
minlst[endPoint] = dist + w
heapq.heappush(heap,(minlst[endPoint],endPoint))
dijkstra(n,k)
print(minlst[k])
처음엔 BFS를 먼저 생각했으나 이동할때마다 걸리는 시간이 다르므로 불가능했다.
다익스트라 알고리즘을 조금 변형해 풀 수 있었다.
2) 백준 11404 : 플로이드
import sys
INF = int(1e9)
n = int(sys.stdin.readline().strip())
m = int(sys.stdin.readline().strip())
floid = [[INF]*n for _ in range(n)]
for i in range(m):
a,b,c = map(int,sys.stdin.readline().strip().split())
if c < floid[a-1][b-1]:
floid[a-1][b-1] = c
def fw(now):
for i in range(n):
for j in range(n):
if i == j:
floid[i][j] = 0
else:
if floid[i][j] > floid[i][now] + floid[now][j]:
floid[i][j] = floid[i][now] + floid[now][j]
for i in range(n):
fw(i)
for i in range(n):
for j in range(n):
if floid[i][j] == INF:
print(0,end = " ")
else:
print(floid[i][j], end = " ")
print()
한 정점에서 다른 정점으로 향하는 최단 경로를 구하는 플로이드-워셜 알고리즘을 공부하고 기본 문제를 풀어봤다.
플로이드-워셜 알고리즘의 시간복잡도가 O(N**3) 이라는 점을 기억하자
3) 백준 1865 : 웜홀
import sys
INF = int(1e9)
t = int(sys.stdin.readline().strip())
for i in range(t):
n,m,w = map(int,sys.stdin.readline().strip().split())
floid = [[INF]*n for _ in range(n)]
for i in range(m):
a,b,c = map(int,sys.stdin.readline().strip().split())
if c < floid[a-1][b-1]:
floid[a-1][b-1] = c
if c < floid[b-1][a-1]:
floid[b-1][a-1] = c
for i in range(w):
a,b,c = map(int,sys.stdin.readline().strip().split())
c = -c
if c < floid[a-1][b-1]:
floid[a-1][b-1] = c
def fw(now):
for i in range(n):
for j in range(n):
if floid[i][j] > floid[i][now] + floid[now][j]:
floid[i][j] = floid[i][now] + floid[now][j]
if i == j and floid[i][j] < 0:
return -1
return 0
answer = "NO"
for i in range(n):
temp = fw(i)
if temp == -1:
answer = "YES"
break
print(answer)
마찬가지로 플로이드-워셜 알고리즘을 이용해 푸는 문제였다.
floyd 스펠링을 몰라서 floid 라고 쓴 건 넘어가자
4) 백준 14500 : 테트로미노
코드 133줄짜리 구현 문제였다.
배열과 반복문을 잘 다루는게 구현 문제를 잘 푸는 방법인 것 같다.
5) 백준 1719 : 택배
import sys
INF = int(1e9)
n,m = map(int,sys.stdin.readline().strip().split())
graph = [[INF]*n for _ in range(n)]
answer = [["-"]*n for _ in range(n)]
for i in range(m):
a,b,c = map(int,sys.stdin.readline().strip().split())
graph[a-1][b-1] = c
graph[b-1][a-1] = c
answer[a-1][b-1] = b
answer[b-1][a-1] = a
def fw(now):
for i in range(n):
for j in range(n):
if i == j:
graph[i][j] = 0
if graph[i][j] > graph[i][now] + graph[now][j]:
graph[i][j] = graph[i][now] + graph[now][j]
answer[i][j] = answer[i][now]
for i in range(n):
fw(i)
for i in range(n):
for j in range(n):
print(answer[i][j] , end = " ")
print()
마찬가지로 플로이드-워셜 알고리즘을 사용해 푸는 문제였다.
특정 정점을 거쳐갔을 때 경로가 더 짧아진다면 배열을 갱신하는 플로이드-워셜 알고리즘의 원리를 잘 기억하자
6) 백준 1916 : 최소비용 구하기
import sys,heapq
INF = int(1e9)
n = int(sys.stdin.readline().strip())
m = int(sys.stdin.readline().strip())
graph = [[] for _ in range(n)]
for i in range(m):
a,b,c = map(int,sys.stdin.readline().strip().split())
graph[a-1].append((b-1,c))
start,end = map(int,sys.stdin.readline().strip().split())
def dijkstra():
minlst = [INF]*n
minlst[start-1] = 0
heap = [(0,start-1)]
while heap:
dist,now = heapq.heappop(heap)
if now == end-1:
print(dist)
return
elif minlst[now] < dist:
continue
else:
for endPoint,w in graph[now]:
if minlst[endPoint] > dist + w:
minlst[endPoint] = dist + w
heapq.heappush(heap,(minlst[endPoint],endPoint))
dijkstra()
간단한 다익스트라 활용문제였다
다익스트라, 플로이드-워셜 알고리즘을 이용한 문제들을 풀어봤는데
확실히 알고리즘의 기본 난이도가 높은 편이라 그런지 응용 문제들을 푸는게 굉장히 까다로워졌다.
지금 4일째 한 문제도 못 풀고 있는데 정체기가 온 것 같다.
2월까지 골드 1 달기로 목표를 바꿔봐야겠다.
'백준 플레를 향해서' 카테고리의 다른 글
플레찍었으니 정리해보는 알고리즘 노트 2 - 중간에서 만나기, 투 포인터 (0) | 2023.02.06 |
---|---|
플레찍었으니 정리해보는 알고리즘 노트 1 - 이진탐색 (0) | 2023.02.05 |
백준 플레를 향해서 - 12월 넷,다섯째주(12.19~12.31) (1) | 2023.01.01 |
백준 플레를 향해서 - 12월 둘째주(12.5~12.11) (2) | 2022.12.11 |
백준 플레를 향해서 - 11월~12월 첫째주(~12.4) (2) | 2022.12.11 |