[백준-2573] 빙산 - Python

 

 

 

문제 소개

 

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

 

 

 

사용한 알고리즘

 

 

BFS 알고리즘 & 부분 업데이트

이번 문제는 시간초과와 메모리초과를 해결하는 부분이 어려웠음
일단은 풀어서 해결을 했지만
풀고나니 별개로 조금더 최적화 할 수 있는 여지가 있는것 같다 (어떤 부분일까?)

 

 

 

 

구상

 

물과 얼음의 위치를 저장해놓은 Arr를 업데이트 할때 

원본 Arr를 복사하지 않고 빙산을 업데이트 하면 안된다.
만약에 동시에 진행이 된다면 근접해 있는 빙산에 대해서 내년에 빙산에서 물이되는 위치가 바로 물로 판정이 되고 근접해 있는 옆빙산에 영향을 주기 때문이다. 

이부분을 알았다면 빙산과 물의 위치를 저장해놓은 Map을 복사해서 2개를 만들어야 한다고 생각 할 수 있다.
왜냐하면 복사본을 만들지 않고 빙산을 업데이트 했을때 빙산에서 물이된 위치가 물로 판정이 되어서 옆 빙산의 물높이 감소에 괜히 -1 만큼의 영향을 주기 때문이다  
아래의 그림으로 표현해 보았다.

 

그래서 Map을 두개를 만든다면 메모리초과 및 시간초과가 나오게 된다. (Python인 경우)
그러면 Map을 하나만큼의 메모리를 사용해서 이 문제를 풀 수 있을까? 
답은 할 수 있다.

위에서 발생했던 문제는 연속된 빙산을 녹이면 안되는것이 문제였다. 
그런데 떨어져 있는 빙산덩어리들은 어떠한가?
서로 떨어져 있기 때문이 떨어진 빙산 덩어리를 업데이트한다고 해서 다른 빙산덩어리에는 영향을 주지 않는다.

따라서 Arr을 하나만 가지고 있는채로
1. Map안에서 빙산덩어리를 탐색하고 (BFS로 탐색)
2. 그 빙산덩어리를 업데이트로 녹이면 된다. (위에 BFS로 탐색하면서 녹이는 정도도 같이 알 수 있음)
그리고 Map안의 다른 빙산덩어리를 찾으면 된다.

이런식으로 업데이트를 서로 영향을 안주는 덩어리들만 순차적으로 업데이트하면 굳이 Map을 복사할 필요가 없다.
아래 그림으로 표현해 보았다.

수도코드를 생각하면 다음과 같이된다.

1. BFS로 얼음 덩어리를 탐색하고
   BFS로 탐색하는중에 인접한 얼음 덩어리와 인접한 물을 양을 알수 있다.
2. 얼음 덩어리가 두개면 return하고 하나면
   그렇게 찾은 큰 얼음 덩어리를 모두 업데이트 한다. -> 1.번으로 간다

 

 

 

Code 

 

#############################################################################
#
#############################################################################

import sys
import collections



sys.stdin = open("input.txt", "r")

input=sys.stdin.readline
years = 0 # 몇 년이 지났는지 판단하는 변수
Xn , Yn = map(int,input().split())
graph   = [[int(n) for n in input().split()] for _ in range(Xn)]

Q = collections.deque([])


movement = ((1,0),(-1,0),(0,1),(0,-1))
def BFS(x,y,visited):
    # [x,y,melt]
    Q.append([x,y])
    visited[x][y]=1
    melt_list = []
    while Q:
        x,y = Q.popleft()
        waterAround = 0
        for dx,dy in movement:
            nx = x + dx
            ny = y + dy
            if 0<= nx < Xn and 0<= ny < Yn  and visited[nx][ny]==0:
                if graph[nx][ny]>0:
                    Q.append([nx,ny])
                    visited[nx][ny]=1
                else:
                    waterAround += 1
        melt_list.append([x,y,waterAround])
    return melt_list



while 1:
    cur_land = 0
    visited = [[0 for _ in range(Yn)] for _ in range(Xn)]
    for x in range(Xn):
        for y in range(Yn):
            if graph[x][y]>0 and visited[x][y]==0:
                cur_land += 1
                melt_ = BFS(x,y,visited)
                for k in range(len(melt_)):
                    mx,my,m = melt_[k]
                    graph[mx][my] = max(graph[mx][my]-m,0)
    if cur_land==0:
        years=0
        break
    if cur_land>=2:
        break
    years += 1


print(years)

 

 

 

마무리

 

반례 모음 

5 7
0 0 0 0 0 0 0
0 3 3 2 3 3 0
0 4 0 4 0 3 0
0 0 0 0 4 3 0
0 0 0 0 0 0 0
0

5 7
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 10 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0

5 7
0 0 0 0 0 0 0
0 3 3 1 3 3 0
0 4 0 4 0 3 0
0 0 0 0 4 3 0
0 0 0 0 0 0 0
1

5 7
0 0 0 0 0 0 0
0 3 6 3 6 7 0
0 3 0 0 0 10 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
2

5 7
0 0 0 0 0 0 0
0 3 6 0 6 7 0
0 3 0 0 0 10 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0

5 7
0 0 0 0 0 0 0
0 9 8 9 8 9 0
0 9 8 9 8 9 0
0 9 8 9 8 9 0
0 0 0 0 0 0 0
0

5 7
0 0 0 0 0 0 0
0 9 8 3 8 9 0
0 9 8 0 8 9 0
0 9 8 9 8 9 0
0 0 0 0 0 0 0
5

5 5
0 0 0 0 0
0 1 0 1 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0

7 7
0 0 0 0 0 0 0
0 1 1 0 1 1 0
0 1 9 1 9 1 0
0 1 1 1 1 1 0
0 1 1 1 1 1 0
0 0 1 1 1 0 0
0 0 0 0 0 0 0
2

더 읽기

• 반례 모음 출처 : https://www.acmicpc.net/board/view/35110

 

 

※ end