빙산 (백준 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

후기

앞분꺼 봤지만 그냥 등수 높아서 좋다 크크

좋은 웹페이지 즐겨찾기