문제풀이
[PY] 2573 : 빙산
pwerty
2025. 4. 10. 23:50
https://www.acmicpc.net/problem/2573
빙(xxxx)산
지난번에 진행이 끝났어야 했던 내용이기에 30분 아이디어 구상, 30분 psudo 완성을 목표로 하려 했는데 의외로 조금씩 풀리는 구석이 있어서 계속 시도하니 뭔가뭔가 됐다. (결국엔 피티 "지" 동원해버리고 말았다)
정석적인 방법은 뭐.. DFS로 덩어리 하나씩 보면서 깎을거 깎고, 그런 식인데. 나도 내가 구상한게 나름 일리가 있는게 있다.
- 입력을 다 받고 while true하에서 계속 순회를 돌리도록한다. 대신에 true 시작 점에서 isFounded를 지정한다.
- isFounded는 0이 아닌 빙산을 찾았을 때만 True가 된다. 만약 False로 for문 순회를 통과했다면 빙산이 아예 없는 것이니 종료한다.
- DFS를 수행하면서 스택에 넣냐마냐를 논하는 동시에 이 칸이 다음 턴에 얼마나 녹을지도 고려 할 수 있다. 그래서 dx dy로 보면서 유효한 범위 내에서 옆에 빙산이면 isVisited여부에 따라 스택에 추가여부를 결정하고, 빙산이 아니면 melt 가중치를 +1 했다. 그리고 모든 방향에 대한 고려가 끝났다면 해당 빙산의 좌표와 melt 가중치를 queue에 push 한다.
- 또 매 DFS에서 stack.pop이 되는 것중 올바른 아이템인 경우 visitedCount를 세도록 했다. 이 루틴에 대해선 진짜 내가 진짜 맛있게 튀겼다고 할 수 있을정도로 천천히 설명해보겠다.
- DFS로 털만큼 털었다면 queue를 털면서 0 이하값들은 0으로 올려치기해서 올바르게 녹은 빙산 처리를 할 수 있도록 한다.
visitedCount, expectedCount, meltedCount를 고려했다
일리있었으나내손으로차마끝내지못했어..
- visitedCount : DFS를 돌며 stack에서 pop된 아이템이 이상이 없으면 +1 된다.
- 즉, 이 변수는 isVisited = True 가 될 때마다 +1 된다.
- meltedCount : queue에서 녹이는 처리를 하는 것은 DFS가 끝나고 이루어져야한다. 여기서 녹은 빙산만큼 +1 해서 세어둔다.
- queue에서 pop해서 녹이는 처리를 했는데, 실질적으로 녹는 애들에 대해서 +1를 하게끔 했다.
- expectedCount : visitedCount와 meltedCount가 정해지면 visitedCount - meltedCount 해서 다음 빙산의 갯수 기댓값으로 등록시킨다.
- 즉, 다음 이 필드에는 expectedCount만큼의 빙산이 남아있지만, 다음 DFS 시도시 빙산 갯수 기댓값으로 expectedCount만큼 도달하지 못했다는건 연결되지 못했다는 상황이 발생한 것이다. 이게 보다 확실한 분리된 빙산 발생으로 적합하다고 생각했다.
자, 완전 첫 DFS때는 expectedCount를 일부러 주지 않았다.
- 첫번째 빙산은 어차피 통째로 한 덩어리의 입력이 있다고 했다.
- 그럼 첫 입력때 세어두고 바로 DFS를 시도할텐데 그 사이에 값 변동이 발생하지 않을 것이고, 또 expectedCount는 첫 값 반영 전 초기화로 0일 것이다.
- 다만, 값을 갱신할거고, 이후로 다시 0이 된다면 그건 진짜 뭐 뭔 일이 난거지 않을까. 그래서 expectedCount를 사용하는 방법을 고려했는데 피티 "지"는 이 부분에 대해 대단히 흡족해했다. 내 자존심 어디갔냐
기존에 아이디어가 정리 안되고 남발되던 내 코드
import sys
input = sys.stdin.readline
from collections import deque
sero, garo = map(int, input().split())
field = [list(map(int, input().split())) for _ in range(sero)]
meltingQueue = deque()
visitedCount = 0
expectedValue = 0
day = 0
stack = []
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
def dfs():
global visitedCount, expectedValue, day, meltingQueue, stack
while stack:
x, y = stack.pop()
if isVisited[x][y]:
continue
isVisited[x][y] = True
visitedCount += 1
meltValue = 0
for i in range(4):
tX = x + dx[i]
tY = y + dy[i]
# 유효한 범위 이내인 경우에만 가능하다
if(0 <= tX < sero and 0 <= tY < garo):
if(field[tX][tY] == 0):
meltValue += 1
else:
if(isVisited[tX][tY] != True):
stack.append([tX, tY])
meltingQueue.append([x, y, meltValue])
if (expectedValue != 0): # 첫 DFS라 expectedValue 비교 X
if(expectedValue != visitedCount):
print(day)
exit()
meltedZoneCnt = 0
while meltingQueue:
valX, valY, val = meltingQueue.popleft()
if(field[valX][valY] - val <= 0):
field[valX][valY] = 0
meltedZoneCnt += 1
else:
field[valX][valY] - val
expectedValue = visitedCount - meltedZoneCnt
day += 1
if expectedValue == 0:
print(day)
exit()
while True:
isVisited = [[False for _ in range(garo)] for _ in range(sero)]
isFounded = False
for i in range(sero):
for j in range(garo):
if field[i][j] != 0 and not isVisited[i][j]:
stack.clear()
visitedCount = 0
isFounded = True
stack.append([i, j])
dfs()
if(isFounded == False):
print(0)
exit()
최종 정리된 코드 ㅠㅠ
import sys
input = sys.stdin.readline
from collections import deque
sero, garo = map(int, input().split())
field = [list(map(int, input().split())) for _ in range(sero)]
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
day = 0
expectedValue = 0
def dfs(x, y):
stack = [(x, y)]
isVisited[x][y] = True
visitedCount = 1
meltingQueue = deque()
while stack:
cx, cy = stack.pop()
meltValue = 0
for dir in range(4):
nx = cx + dx[dir]
ny = cy + dy[dir]
if 0 <= nx < sero and 0 <= ny < garo:
if field[nx][ny] == 0:
meltValue += 1
elif not isVisited[nx][ny]:
isVisited[nx][ny] = True
visitedCount += 1
stack.append((nx, ny))
meltingQueue.append((cx, cy, meltValue))
meltedZoneCnt = 0
while meltingQueue:
mx, my, melt = meltingQueue.popleft()
if field[mx][my] - melt <= 0:
field[mx][my] = 0
meltedZoneCnt += 1
else:
field[mx][my] -= melt
return visitedCount, meltedZoneCnt
while True:
isVisited = [[False] * garo for _ in range(sero)]
isFounded = False # 빙산 찾았는지 여부
for i in range(sero):
for j in range(garo):
if field[i][j] != 0 and not isVisited[i][j]:
isFounded = True
visitedCount, meltedZoneCnt = dfs(i, j)
if expectedValue != 0 and expectedValue != visitedCount:
print(day)
sys.exit()
expectedValue = visitedCount - meltedZoneCnt
if expectedValue == 0: # 전부 녹음
print(0)
sys.exit()
day += 1
if not isFounded: # 빙산 자체가 없음
print(0)
sys.exit()