빙산 (백준 2573번 파이썬)
스택에 i와 j 순서 잘못 써서 이거 찾아내는 데 하루 다 걸렸숴!!! 끄아!!!
코딩하면서 제일 허무할 때야 ㅠㅠ 로직 잘못된 줄 알고 while문만 겁나게 디버깅했는데 흑흑
이런 실수는 꼭 줄이자...
풀이
필요 요소
1. li: 데이터 담을 2차원 배열
2. year: while문 돈 만큼 올려주는 연도 변수
3. tmp_li: 변화된 빙하 데이터를 일년 단위로 담아서 변경해줄 2차원 배열
4. all_num: 빙하가 몇 개 남았는지 세줄 변수
5. count: 현재 년도의 빙하 개수를 세어줄 변수(모자르면 2개로 짤린 거)
6. water: 빙하 주변에 물이 몇 군데인지 세줄 변수
7. plus_water: 빙하가 물로 변한 개수
로직
1. 2차원 배열에 담고
2. 매년 while문에서 한 번 돌 때마다 1년씩 올려주고
3. 첫 빙하 위치 찾고 스택에 넣고
4. while문을 또 돌려주면서 스택에 든 값을 뽑아주는데
5. 돌 때마다 count값을 올려 나중에 다 돌았는지 확인해준다.
4. 스택에서 뽑은 값 상하좌우에 물이 있으면 있는만큼 수를 더하고
5. 빙하가 있으면 그 빙하를 스택에 넣고 이미 왔다고 check변수에 체크해주고 스택에 넣어준다.
6. 스택에서 뽑은 값에서 주변에 물웅덩이가 있는만큼 빼준다.
7. 안쪽 while문에서 배열값을 바꾸면 아직 1년이 지나지도 않았는데 옆칸에 영향을 주므로
8. 다른 배열에 임시적으로 사용해준다.
9. 스택값이 없으면 count값과 빙하 전체 개수 변수를 비교하고
10. 같고 count가 0이면 0출력
11. 같고 count가 0보다 크면 1년 올려주고
12. 빙하 전체 개수에서 올해 물로 바뀐 빙하의 수를 빼준다.
코드
from sys import stdin
Y , X = map(int, stdin.readline().split())
stack = []
li = [list(map(int, stdin.readline().split()))for _ in range(Y)]
tmp_li = li
dx, dy = [0,0,1,-1], [1,-1,0,0]
year = 0
all_num = 0
for i in range(Y):
for j in range(X):
if li[i][j]!=0:
all_num+=1
while True:
li = tmp_li
check =[[0]*X for _ in range(Y)]
flag = 0
for i in range(Y):
for j in range(X):
if li[i][j] != 0:
stack.append((j,i))
flag = 1
break
if flag:
break
count = 0
plus_water =0
cnt =0
while stack:
x,y = stack.pop()
check[y][x] =1
water = 0
count+=1
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<= nx <X and 0 <= ny <Y and check[ny][nx]==0:
if li[ny][nx] == 0:
water +=1
else:
stack.append((nx,ny))
check[ny][nx] = 1
# 빼줘
if tmp_li[y][x]-water >0:
tmp_li[y][x]-=water
else:
tmp_li[y][x] = 0
plus_water+=1
if count == all_num:
if count ==0:
print(0)
break
else:
year+=1
else:
print(year)
break
all_num -= plus_water
후기
앞분꺼 봤지만 그냥 등수 높아서 좋다 크크
Author And Source
이 문제에 관하여(빙산 (백준 2573번 파이썬)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@grace0st/빙산-백준-2573번-파이썬저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)