🧭 To-do List
✅ 백준 풀기 | 2573 빙산, 2178 미로 탐색
✅ 키워드 공부 | 다익스트라
내일
☑️ 위상 정렬 문제 풀어보기
📝 배운 것들
🏷️ 다익스트라
- 출발 노드를 설정한다
- 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다
- 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다
- 해당 노드를 거쳐서 특정한 노드를 가는 경우를 고려하여 최소 비용을 갱신한다
- 위 과정에서 3번~ 4번을 반복한다
(귀류법으로 납득해보기 - 영상 9분 경)
3번까지의 최소 거리가 1 -> 3이 아니라 1 -> 2 -> 3 이었다면
애초에 2번으로 갔지 3번으로 가지 않았다.
비용이 갱신되면 이전 방문 노드들 업데이트
그냥 쭉 따라가면 위와 같이 노드 4와 5가 잘못된 비용 계산을 하게 된다.
비용이 갱신될 때마다 이전에 방문했던 노드들을 확인해야함.
🏷️ 반복문 줄이는 법
if Arctic[i+1][j] != 0: meltN -= 1
if Arctic[i-1][j] != 0: meltN -= 1
if Arctic[i][j+1] != 0: meltN -= 1
if Arctic[i][j-1] != 0: meltN -= 1+1, -1을 dx, dy로 줄일 수 있다.
dx = [1,0,-1,0]
dy = [0,1,0,-1]
for k in range(4):
if Arctic[i+dx[k]][j+dy[k]]엄청 간단한 if문 4개 정도면 위도 괜찮겠지만 많아지면 아래가 불가피해질듯.
⚔️ 백준
📌 2573 빙산
1. 이전에 풀어봤던 문제 떠올림 (안전 영역)
2. 문제 기반으로 상하좌우 검색하는 식으로 구현했더니 시간 초과
3. dfs라고 적혀 있었으니 dfs로 구현해보기로 함
4. 인접 노드들이 몇 개 있는지로 녹이는 높이 결정
5. 노드 구현 여러 방법 중 class가 자신 있어서 class로 구현옆자리 실력자 동기에게 사고과정이 어떻게 되냐고 물어봤더니 대충 이런 식이었음.
너무 다른 사람의 사고과정에 환상을 갖지 말고
천천히 구현해보며 풀자.
못하면 못하는대로 천천히 나아가면 될듯.
빙산은 1년이 지날 때마다 기본적으로 높이 -4
옆에 있는 빙산 하나마다 녹는 높이 1씩 줄어듦
빙산 위치 구현 방법
인접 행렬
인접 리스트
딕셔너리
노드
빙산 녹이려면
옆에 빙산이 있는지 확인
한 덩어리인지 확인하려면
bfs내가 생각했던 풀이과정
class Node:
def __init__(self, i, j, height):
self.locate = (i,j)
self.height = height
self.near = []
N, M = map(int, input().split())
Arctic = []
Icebergs = []
# 북극 상황 받아오기
for _ in range(N):
field = list(map(int,input().split()))
Arctic.append(field)
# 노드 만들기
for i in range(N):
for j in range(M):
height = Arctic[i][j]
if height != 0:
# 빙산 높이 대신 노드 넣고 빙산 명단 만들기
Arctic[i][j] = Node(i, j, height)
Icebergs.append((i,j))
# Arcitc 행렬에 자식 노드 좌표 넣기
for iceberg in Icebergs:
i, j = iceberg[0], iceberg[1]
iceberg = Arctic[i][j]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
for k in range(4):
near_iceberg = Arctic[i+dx[k]][j+dy[k]]
if near_iceberg != 0:
iceberg.near.append(near_iceberg)
print(Arctic)
def one_iceberg():
return False
# 빙하 녹이기
def melting():
# 높이 줄이기
for iceberg in Icebergs:
i, j = iceberg[0], iceberg[1]
iceberg = Arctic[i][j]
meltH = 4
for near in iceberg.near:
meltH -= 1
iceberg.height -= meltH
# 높이가 0 이하로 줄어든 빙산은 Arctic, Icebergs, near에서 삭제
for iceberg in Icebergs:
i, j = iceberg[0], iceberg[1]
iceberg = Arctic[i][j]
if iceberg.height <= 0:
Arctic[i][j] = 0
Icebergs.remove((i,j))
for
melting()
# 자식을 노드로 달아야 하는데
# 확인할 수 있는 건 좌표 뿐임
# 좌표에 노드를 넣는다면? 북극 좌표들을 전부 순회해야 노드들을 알 수 있음
# Icebergs에는 빙산의 좌표들만 넣으면 될듯적으면서 또 저번에 풀었던 거랑 똑같이 이상하게 가고 있다는 걸 눈치챘는데
"높이가 0 이하로 줄어든 빙산은 Arctic, Icebergs, near에서 삭제"
여기 코드 적다가 애초에 접근 방식이 틀렸다는 걸 깨달음.
정점(빙산)의 연결 관계만 만들고 나면 좌표는 필요 없을듯.
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
class Node:
def __init__(self, i, j, height):
self.locate = (i,j)
self.height = height
self.near = set()
N, M = map(int, input().split())
Arctic = []
Icebergs = set()
# 북극 상황 받아오기
for _ in range(N):
field = list(map(int,input().split()))
Arctic.append(field)
# 노드 만들기
for i in range(N):
for j in range(M):
height = Arctic[i][j]
if height != 0:
# 빙산 높이 대신 노드 넣고 빙산 명단 만들기
Arctic[i][j] = Node(i,j,height)
Icebergs.add(Arctic[i][j])
# 인접 노드 연결해주기
for iceberg in Icebergs:
i, j = iceberg.locate[0], iceberg.locate[1]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
for k in range(4):
near_iceberg = Arctic[i+dx[k]][j+dy[k]]
if near_iceberg != 0:
iceberg.near.add(near_iceberg)
# 빙하 녹이기
def melting():
# 높이를 낮추고
for iceberg in Icebergs:
if iceberg != 0:
melt_h = 4 - len(iceberg.near)
iceberg.height -= melt_h
# 0 이하로 낮아지면 Arctic, near들의 near에서 삭제
deleteQ = []
for iceberg in Icebergs:
if iceberg.height <= 0:
for n in iceberg.near:
n.near.remove(iceberg)
i, j = iceberg.locate[0], iceberg.locate[1]
Arctic[i][j] = 0
deleteQ.append(iceberg)
# Icebergs에서 삭제
for d in deleteQ:
Icebergs.remove(d)
# dfs
def dfs(ice, visited):
global cnt
visited.add(ice)
cnt += 1
if (len(ice.near) == 0):
return
for near in ice.near:
if near not in visited:
dfs(near, visited)
year = 0
while True:
melting()
year += 1
cnt = 0
# 끝까지 다 녹았는가?
if len(Icebergs) == 0:
year = 0
break
else:
dfs(next(iter(Icebergs)),set())
# 두 덩이로 나눠졌는가?
if len(Icebergs) != cnt:
break
print(year)↑ 정답 코드
첫 완성 후 문제 1. 문제 조건
만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.
라는 문제 조건에 맞게 수정함
첫 완성 후 문제 2. 끝없는 시간 초과
list로 되어있는 것들 죄다 set로 바꿔보다가
dfs에 쓰이는 visited 리스트를 set로 바꿨더니 정답처리됨.
생각해보니 저번에 내 dfs 코드로 visited 디버깅 찍어봤더니
visited에 중복이고 뭐고 끝없이 값이 추가되고 있었음.
not in visited 구문이 코드에 존재하는데,
이것을 각 빙산의 근접 빙산을 순회할 때마다 그 긴 배열을 점검해야해서
성능이 느려졌던 것 같다.
다른 코드보니 노드 쓰는게 아니라 좌표만으로 풀면 훨씬 쉬웠을듯
📌 2178 미로 찾기
if graph[x+dx][y+dy] == '1':실수 1.
문자열 1하고 숫자 1하고 달라서 if문이 넘어가질 못했었다.
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [input().strip() for _ in range(N)]
from collections import deque
def bfs(node, end, visited, waiting):
visited.add(node)
waiting.append(node)
while len(waiting) != 0:
global cnt
qSize = len(waiting)
cnt += 1
for _ in range(qSize):
# 큐에서 확인할 칸을 하나 꺼낸다
node = waiting.popleft()
# print(node)
# 도착 지점이었다면 경로를 표시하고 다음으로 넘어간다
if node == end:
return cnt
# 상하좌우 칸을 확인한다
x, y = node[0], node[1]
dx_list = [-1,1,0,0]
dy_list = [0,0,-1,1]
for i in range(4):
dx, dy = dx_list[i], dy_list[i]
# 상하좌우 중에 유효한 칸이 있으면 큐에 넣는다
if 0 <= x+dx <= N-1 and 0 <= y+dy <= M-1:
next = (x+dx,y+dy)
if next not in visited:
if graph[x+dx][y+dy] == '1':
waiting.append((x+dx,y+dy))
visited.add((x+dx,y+dy))
return cnt
visited = set()
waiting = deque()
cnt = 0
print(bfs((0,0), (N-1,M-1), visited, waiting))↑ 정답 코드
qSize = len(waiting)
cnt += 1
for _ in range(qSize):bfs의 depth를 측정하는 방법을 떠올려내지 못해서 동기에게 물어봤더니
while문을 따로 빼고 큐 사이즈만큼 반복시키는 방법을 알려줬다.
간단하기는 한데 못 떠올려냈을듯?
# 도착 지점이었다면 경로를 표시하고 다음으로 넘어간다
if node == end:
return cntreturn이 아니라 break를 썼더니 끝 점을 찾고도 진행을 더 못할 때까지
진행하는 경우가 생겼었다.
