728x90
1. 다익스트라 알고리즘(Dijkstra algorithm)
모든 간선에 대한 가중치가 항상 0이상임을 가정하고 두 꼭짓점 간의 가장 짧을 경로를 찾는 알고리즘
- 간선 완화(Edge Relaxation)
- 시작 정점 s에서 다른 정점 v까지의 초기 거리 값을 부여하고 단계를 거듭하여 개선시키는 것
- 간선 (u, v)를 완화하는 과정
- u를 통해 v까지 가는 지금까지 발견된 최단 경로를 개선할 수 있는지 검사
- 개선할 수 있다면, v의 최단 경로 추정값을 갱신한다.
- 시간복잡도 O(|E| + |V|log|V|)
< 참고 > https://ko.wikipedia.org/wiki/데이크스트라_알고리즘
1. 다익스트라를 이용한 문제 풀이
import sys
import heapq
N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
bus = [[] for _ in range(N)]
for _ in range(M) :
s, e, w = map(int, sys.stdin.readline().split())
bus[s-1].append((e-1, w))
start, end = map(int, sys.stdin.readline().split())
def dijkstra(start, end) :
# start를 시작으로 각 정점까지의 최단 거리 저장
# 초기화 과정
distance = [float('inf')] * N
queue = []
distance[start] = 0 # 시작점 거리 0으로 초기화
heapq.heappush(queue, (distance[start], start))
while queue :
cur_dis, cur_idx = heapq.heappop(queue)
# 현재 거리가 출발지부터 현재까지의 거리보다 작거나 같을 경우
# 같아야 하는 이유는 처음에는 cur_dis와 distance[cur_idx]가 같을 수 밖에 없다.
# 기존의 거리보다 더 짧은 값이 나타날 경우
if cur_dis <= distance[cur_idx] :
for idx, weight in bus[cur_idx] :
# 간선 완화 과정
# 지금까지 발견된 최단 거리보다 idx 노드를 통해 가는 길이 더 짧을 경우
# 최단 거리 갱신
if cur_dis + weight < distance[idx] :
distance[idx] = cur_dis + weight
heapq.heappush(queue, (distance[idx], idx))
return distance[end]
print(dijkstra(start-1, end-1))다익스트라 알고리즘을 이해하고 구현해봤는데 한가지를 생각하지 못해서 블로그를 참고하여 구현을 완료했다.
내가 생각못한 것은 if cur_dis <= distance[cur_idx]의 조건이었다. 처음에는 visited를 사용하여 하려고 했는데 코드가 계속 꼬여
답을 도출하지 못했다. cur_dis > distance[cur_idx] 된다는 의미는 현재 distance[cur_idx]가 최소라는 의미로 넘기면 된다.
그러므로 작거나 같으면 동작을 실행하도록 구현했다.
<참고 블로그 >
https://justkode.kr/algorithm/python-dijkstra/
visited를 사용한 다익스트라 구현 : https://techblog-history-younghunjo1.tistory.com/247
▶ 다익스트라 알고리즘을 이용한 풀이
import sys
import heapq
n = int(sys.stdin.readline())
# 0 : 검은방(갈 수 없음) 1 : 흰방
miro = [list(sys.stdin.readline()) for _ in range(n)]
def dijkstra(x, y) :
visited = [[0]*n for _ in range(n)]
queue = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited[x][y] = 1
heapq.heappush(queue, (visited[x][y], x, y))
while queue :
# 최소 비용을 갖는 경로부터 확인한다.
cur_cost, curX, curY = heapq.heappop(queue)
for i in range(4) :
nx, ny = curX + dx[i], curY + dy[i]
if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == 0:
if miro[nx][ny] == '1': # 흰방이면 비용이 증가할 필요가 없다.
visited[nx][ny] = cur_cost
else : # 검은방이면 비용을 1 증가시켜야 한다.
visited[nx][ny] = cur_cost+1
heapq.heappush(queue, (visited[nx][ny], nx, ny))
return visited[n-1][n-1]-1 # 1부터 시작하여 마지막에 1 빼주기
print(dijkstra(0, 0))시작 좌표부터 도착 좌표까지 가야하는데 부수고 가야할 경우가 존재한다. 즉, 부수는 비용이 최저가 되는 경우를 구해야한다.
다익스트라 알고리즘을 이용하는데 시작점부터의 거리를 기준으로 하는게 아니라 비용을 기준으로 알고리즘을 작성한다.
< 참고 > https://kimmeh1.tistory.com/545
▶ BFS를 이용한 풀이
import sys
from collections import deque
n = int(sys.stdin.readline())
# 0 : 검은방(갈 수 없음) 1 : 흰방
miro = [list(sys.stdin.readline()) for _ in range(n)]
def bfs(x, y) :
visited = [[0]*n for _ in range(n)]
queue = deque()
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited[x][y] = 1
queue.append((x, y))
while queue :
curX, curY = queue.popleft()
for i in range(4) :
nx, ny = curX + dx[i], curY + dy[i]
if 0 <= nx < n and 0 <= ny < n :
if visited[nx][ny] == 0 :
if miro[nx][ny] == '1' :
visited[nx][ny] = visited[curX][curY]
queue.appendleft((nx, ny))
else :
visited[nx][ny] = visited[curX][curY]+1
queue.append((nx, ny))
return visited[n-1][n-1]-1
print(bfs(0,0))따지고 보면 다익스트라이다. deque()를 사용하므로 비용이 변경되지 않을 경우에는 앞에서 추가하고 비용이 증가할 경우
뒤에서 추가해서 비용이 작은 것을 먼저 탐색하도록 한다.
< 참고 > https://it-garden.tistory.com/275
3. 그래프 문제풀이(BFS)
1. 7596번 - 토마토
import sys
from collections import deque
M, N, H = map(int, sys.stdin.readline().split())
tomato = [[list(map(int, sys.stdin.readline().split())) for _ in range(N)] for _ in range(H)]
dx = [-1, 1, 0, 0, 0, 0]
dy = [0, 0, -1, 1, 0, 0]
dh = [0, 0, 0, 0, -1, 1]
visited = [[[0]*M for _ in range(N)] for _ in range(H)]
def bfs() :
while queue :
curX, curY, curH = queue.popleft()
for i in range(6) :
nx, ny, nh = curX + dx[i], curY + dy[i], curH + dh[i]
if 0 <= nx < N and 0 <= ny < M and 0 <= nh < H :
if visited[nh][nx][ny] == 0 and tomato[nh][nx][ny] == 0 :
tomato[nh][nx][ny] = tomato[curH][curX][curY] + 1
visited[nh][nx][ny] = 1
queue.append((nx, ny, nh))
def getDay() :
day = 0
for i in range(H) : # 높이
for j in range(N) : # 행
for k in range(M) : # 열
if tomato[i][j][k] == 0 : # 안 익은 토마토 존재
print(-1)
return
if day < tomato[i][j][k] :
day = tomato[i][j][k]
if day > 0 :
day -= 1 #1부터 시작했기 때문에 1 빼주기
print(day)
queue = deque()
for i in range(H) : # 높이
for j in range(N) : # 행
for k in range(M) : # 열
if visited[i][j][k] == 0 and tomato[i][j][k] == 1 :
queue.append((j, k, i)) # 처음부터 1로 시작하는 모든 경우 큐에 삽입
visited[i][j][k] = 1
bfs()
getDay()for 문이 너무 많이 사용되서 걱정했는데 다른 사람의 풀이를 보니 다 비슷하게 풀어서 다행이다...
2. 3055번 - 탈출
import sys
from collections import deque
R, C = map(int, sys.stdin.readline().split())
# 입력받은 맵
arr = [list(sys.stdin.readline().strip()) for _ in range(R)]
forest = [[-1]*C for _ in range(R)] # 고슴도치의 경로를 알아낼 그래프
water = [[-1]*C for _ in range(R)] # 시간에 따른 물의 높이를 알아낼 그래프
queue = deque() # water에 사용할 큐
fqueue = deque() # forest에 사용할 큐
end = [] # 도착 좌표 지정
'''
비어있는 곳 .
물이 차 있는 구역 *
돌 X
비버의 굴 D = 도착해야할 곳
고슴도치 위치 S = 시작할 곳
'''
for i in range(R) :
for j in range(C) :
if arr[i][j] == '*' :
queue.append((i, j))
water[i][j] = 0 # 처음부터 물이 차있는 경우
elif arr[i][j] == 'D' :
# 고슴도치가 도착해야할 장소
# 물이 찰 수 없는 공간
end = [i, j]
elif arr[i][j] == 'S' :
fqueue.append((i, j)) # 시작 좌표 큐에 삽입
forest[i][j] = 0 # 이미 고슴도치가 위치한 곳
# 물이 차오를 수 있는 지역이므로 표현을 바꿔준다.
arr[i][j] = '.'
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 물이 차오르는 시간을 측정하는 함수
def water_bfs() :
while queue :
curX, curY = queue.popleft()
for i in range(4) :
nx, ny = curX + dx[i], curY + dy[i]
# 물이 차오르지 못하는 지역 = 비버의 집(D), 돌(X)
# 그 외의 지역을 . 으로 표현
if 0 <= nx < R and 0 <= ny < C and water[nx][ny] == -1 and arr[nx][ny] == '.':
water[nx][ny] = water[curX][curY] + 1
queue.append((nx, ny))
# 고슴도치의 이동 시간을 측정하는 함수
def forest_bfs() :
while fqueue :
curX, curY = fqueue.popleft()
for i in range(4) :
nx, ny = curX + dx[i], curY + dy[i]
# 고슴도치는 다음에 물이 차지 않을 지역으로만 가능하고 움직일 수 있는 지역으로는 . 과 D만 존재한다.
if 0 <= nx < R and 0 <= ny < C and forest[nx][ny] == -1 and (arr[nx][ny] == '.' or arr[nx][ny] == 'D') :
# 현재 이동한 시간에 1을 더한 것보다 다음 이동할 지역이 물에 차는 시간이 크면
# 다음날에 잠길일이 없으므로 이동 가능
# 물에 아예 잠기지 않는 지역이 있을 수 있으므로 or 조건 추가
if forest[curX][curY] + 1 < water[nx][ny] or water[nx][ny] == -1 :
forest[nx][ny] = forest[curX][curY] + 1
fqueue.append((nx, ny))
water_bfs()
forest_bfs()
if forest[end[0]][end[1]] == -1 :
print("KAKTUS")
else :
print(forest[end[0]][end[1]])다른 BFS 한번으로 구하는 코드는 많았는데 참고 블로그에 설명이 너무 잘되어 있고 우선 직관적으로 이해하기 쉬워서
아래의 블로그를 참고하여 코드를 작성했다.
물이 차오르는 시간을 저장하는 water 를 구한 후
고슴도치가 이동할 때 이를 이용하여 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 라는 조건을 만족하도록 한다.
우선 생각 못했던 것은 입력받은 내용을 활용할 수 있도록 정리하는 방식을 완벽하게 생각해내지 못했고 BFS를 두번하여 구할 생각은 아예 하지도 않았었다. 하지만 생각해보면 차근차근히 필요한 것을 정리하다보면 저렇게 코드를 구현한 이유를 알았다.
좀 더 문제를 정리하면서 푸는 습관을 들여야겠다.
< 참고 > https://kyun2da.github.io/2020/09/22/escape/
3. 2294번 - 동전2
import sys
from collections import deque
n, k = map(int, sys.stdin.readline().split())
# 중복 제거를 위해 set 사용
coin = list(set(int(sys.stdin.readline()) for _ in range(n)))
coin.sort()
queue = deque()
for c in coin :
# (현재 코인의 값, 만드는데 쓰인 동전 개수)
# 구해야 할 값보다 작은 것만 저장
if c <= k :
queue.append((c, 1))
def bfs() :
# 인덱스 = cost 즉, 인덱스만큼의 가치를 가진 동전의 최소 개수를 이미 찾았다.
visited = [0] * (k+1)
while queue :
cost, count = queue.popleft()
# 원하는 가치를 가진 값이 등장하면 바로 반환
if cost == k :
return count
for c in coin :
# k보다 작거나 같고 아직 최소 개수를 찾지 못했으면
if cost + c <= k and visited[cost+c] == 0 :
visited[cost+c] = 1
queue.append((cost+c, count + 1))
return -1 # 결국 못찾았으면
print(bfs())어렵게 생각한 것과 달리 동작은 간단했다. 그림과 같이 계속해서 큐에 삽입과 삭제를 반복하다가 원하는 값을 찾으면 함수 종료
이때 visited를 사용하여 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 라는 조건을 만족하도록 한다.
< 참고 > https://alpyrithm.tistory.com/81
728x90
'KraftonJungle2기 > Today I Learned' 카테고리의 다른 글
| [TIL] 위상 정렬 문제 풀이 + Computer System2 (0) | 2023.04.26 |
|---|---|
| [TIL] Algorithm - 위상 정렬 + 플로이드-워셜 (1) | 2023.04.25 |
| [TIL] 그래프 문제 문제 풀이 (0) | 2023.04.22 |
| [TIL] Algorithm - 최소 신장 트리 + 그래프 기본 문제 풀이 (1) | 2023.04.21 |
| [TIL] Graph + 트리 순회 (0) | 2023.04.20 |
