[백준] 2573 : 빙산 python

아이디어를 떠올리는 건 어렵지 않았지만 코드를 써가면서 반복문이 이렇게 많이 나오는 게 맞나..싶었다.

처음 제출한 코드가 시간초과가 나와서 역시 너무 비효율적이었구나 했는데

다른 사람들의 풀이를 참고해봐도 시간초과가 나오더라.

해결방법은 pypy3로 제출하는 거였다.

 

 

NxM 사이즈의 cnt 리스트를 하나 만들고 BFS 탐색을 하다가 인접한 칸 중에 0인 게 있으면

cnt 리스트의 해당 위치값을 1씩 증가시켜두고, 빙산의 높이를 한 번에 바꿔주는 게 핵심이다.

 

 

모든 빙산이 녹았다는 걸 판단하기 위한 방식에 대해 고민을 많이 했었다.

total = 0
# graph는 NxM 사이즈의 리스트
for g in graph:
	total += sum(graph)
if total==0:
	# 모든 빙산이 녹았으니 0을 출력

처음에는 이런 방식으로 2차원 리스트 graph의 총합을 이용해볼까 했는데 너무 비효율적인 것 같았다.

그래서 서치를 하다보니 bfs함수가 수행될 때마다 result 리스트에 1을 append()하는 방법을 보게 되었고 적용해보았다.

 

 

from collections import deque
import sys
input = sys.stdin.readline

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

n,m = map(int,input().split())
graph = []
for i in range(n):
    graph.append(list(map(int,input().split())))

def bfs(a,b):
    queue = deque()
    queue.append((a,b))
    visited[a][b] = 1
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            # 아직 방문하지 않은 칸이 있다면 탐색
            if 0<=nx<n and 0<=ny<m and visited[nx][ny]==0:
            	# 빙산일 경우에는 큐에 추가함
                if graph[nx][ny]!=0:
                    queue.append((nx,ny))
                    visited[nx][ny] = 1
                # 바다일 경우 바다의 개수를 1 증가시킴
                else:
                    cnt[x][y] +=1
    # bfs 수행을 마쳤다는 의미로 1을 리턴함
    return 1

year = 0

while True:
    visited = [[0]*m for i in range(n)]
    cnt =[[0]*m for i in range(n)]
    result = []

	# 모든 빙산을 탐색할 때까지 bfs를 수행함
    for i in range(n):
        for j in range(m):
            if not visited[i][j] and graph[i][j]!=0:
                result.append(bfs(i,j))

	# 빙산의 높이를 한번에 업데이트해줌
    # 빙산의 높이는 0보다 작아질 수 없기 때문에 max 함수를 사용했음
    for i in range(n):
        for j in range(m):
            graph[i][j] = max(0,graph[i][j]-cnt[i][j])
    
    # 얼음 덩어리의 개수가 2개 이상이거나 아예 없는 경우 반복문 종료
    if len(result)>=2 or len(result)==0:
        break
        
	# 1년을 증가시킴
    year+=1

# 얼음 덩어리의 개수가 2개 이상이라면 년수를 출력함
if len(result)>=2:
    print(year)
else:
    print(0)