[백준 2573번] 빙산(파이썬)

https://www.acmicpc.net/problem/2573

2573번: 빙산

이 문제에서 구현해야할 것은 크게 두 가지.

 

1. 빙산을 녹인다.

2. 빙산의 덩어리를 찾는다.

 

1. 빙산을 녹인다.

인접한 공간에 0이 있는지 확인하고

0이 있다면 -1

단, 빙산은 0에서 더 이상 뺼 수 없습니다. 

이런 류의 문제는 deepcopy를 써주면 좋습니다.

만약 빙산을 받은 리스트에

0을 기준으로 지우다보면

위의 같은 NG케이스가 생깁니다.

원래는 0이 인접한 게 2개였는데

앞서 빙산이 녹으면서 0이 되면서

인접한 게 3개가 되면서

-2가 아닌 -3이 되버릴 수 있습니다.

while True:
    tmp_room=deepcopy(room)
    #1. 빙산을  녹임.
    for x,y in ice:
        if room[x][y]==0:
            continue

        for d in range(4):
            nx=x+dx[d]
            ny=y+dy[d]

            if nx<0 or nx>=N or ny<0 or ny>=M:
                continue

            if room[nx][ny]==0:
                if tmp_room[x][y]-1>=0:
                    tmp_room[x][y]-=1
    time+=1
    room=deepcopy(tmp_room)

저 같은 경우에는 0이 된 ice를 그대로 냅둬봤습니다.

그 대신 0이 된 ice는 스킵하는 식으로 구했죠.

while True:
    tmp_room=deepcopy(room)
    tmp_ice=deepcopy(ice)
    #1. 빙산을  녹임.
    for x,y in ice:
        for d in range(4):
            nx=x+dx[d]
            ny=y+dy[d]

            if nx<0 or nx>=N or ny<0 or ny>=M:
                continue

            if room[nx][ny]==0:
                if tmp_room[x][y]-1>0:
                    tmp_room[x][y]-=1
                elif tmp_room[x][y]-1==0:
                    tmp_room[x][y]=0
                    p=tmp_ice.index([x,y])
                    tmp_ice.pop(p)
    time+=1
    room=tmp_room
    ice=tmp_ice

이건 0이 된 빙산을 빼주면서

ice리스트를 다듬어보는 구조.

시간초과 이슈 해결때문에 시도해봤습니다.

 

 

2. 녹인 빙산의 덩어리

이 부분이 시간초과가 많이 난다고 생각했습니다.

처음에는 가로 세로 지도에

빙산이 보이면 큐에 넣고 bfs를 시도했으나

시간이 많이 걸린다고 생각했습니다.

#2. 녹인 빙산이 몇 덩어리인지 보기
visited=[[False]*M for _ in range(N)]
q=deque()
dung=0
out=0
for x,y in ice:
    if visited[x][y]==True:
        continue
    dung+=1

    if dung>=2:
        out=1
        break
    q.append([x,y])
    visited[x][y]=True
    while q:
        px,py=q.popleft()

        for d in range(4):
            nx=px+dx[d]
            ny=py+dy[d]

            if nx<0 or nx>=N or ny<0 or ny>=M:
                continue

            if visited[nx][ny]==True:
                continue

            if room[nx][ny]==0:
                continue

            q.append([nx,ny])
            visited[nx][ny]=True


if out==1:
    break

 

그래서 q에 빙산의 좌표를 넣고 돌리는 식으로 구현했습니다.

이미 방문한 빙산은 넘기는 식으로요.

그런데...

이렇게 구현해도 시간초과가 떴습니다.

대체 뭐지...

하다가...

마지막 부분을 보면 저렇게 나와있습니다.

즉, 두 덩이를 만들기전에

빙산이 다 녹으면 0을 출력하는 걸 구현하지 않으니

시간초과가 자꾸 나버린 거죠.

 

#백준 2573번 빙산
from collections import deque
from copy import deepcopy
N,M=map(int,input().split())

room=[]
ice=[]

dx=[0,0,1,-1]
dy=[1,-1,0,0]

for i in range(N):
    data=list(map(int,input().split()))
    room.append(data)

    for j in range(M):
        if not data[j]==0:
            ice.append([i,j])



time=0
while True:
    tmp_room=deepcopy(room)
    tmp_ice=deepcopy(ice)
    #1. 빙산을  녹임.
    for x,y in ice:
        for d in range(4):
            nx=x+dx[d]
            ny=y+dy[d]

            if nx<0 or nx>=N or ny<0 or ny>=M:
                continue

            if room[nx][ny]==0:
                if tmp_room[x][y]-1>0:
                    tmp_room[x][y]-=1
                elif tmp_room[x][y]-1==0:
                    tmp_room[x][y]=0
                    p=tmp_ice.index([x,y])
                    tmp_ice.pop(p)
    time+=1
    room=tmp_room
    ice=tmp_ice
   #만약 빙산이 다 녹았다면??
    zero=0
    for x in range(N):
        if room[x].count(0)==M:
            zero+=1

    if zero==N:
        time=0
        break
    #2. 녹인 빙산이 몇 덩어리인지 보기
    visited=[[False]*M for _ in range(N)]
    q=deque()
    dung=0
    out=0
    for x,y in ice:
        if visited[x][y]==True:
            continue
        dung+=1

        if dung>=2:
            out=1
            break
        q.append([x,y])
        visited[x][y]=True
        while q:
            px,py=q.popleft()

            for d in range(4):
                nx=px+dx[d]
                ny=py+dy[d]

                if nx<0 or nx>=N or ny<0 or ny>=M:
                    continue

                if visited[nx][ny]==True:
                    continue

                if room[nx][ny]==0:
                    continue

                q.append([nx,ny])
                visited[nx][ny]=True


    if out==1:
        break


print(time)

 

전체 코드입니다.

pypy3로 제출하였습니다.

https://wookcode.tistory.com/m/155

[백준] 2573번, 빙산 (Python)

출력조건에 대한 것이

문제를 푸는 입장에서는 놓치기 쉬워서

난감했던 문제.

출력 조건도 꼼꼼히 봐야겠네요.