백준 2573 python [빙산]

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

BFS

import sys
from collections import deque

# with open("./data.txt", "r") as file:
#     def input():
#         return file.readline().strip()
    
def input():
    return sys.stdin.readline()

def bfs(x, y):
    Q = deque()
    Q.append((x, y))
    visited[y][x] = True

    while Q:
        nowX, nowY = Q.popleft()
        
        for i in range(4):
            newX = nowX + moveX[i]
            newY = nowY + moveY[i]

            if(newY >= N or newY < 0 or newX >= M or newX < 0):
                continue

            if(visited[newY][newX]):
                continue
            
            if(maps[newY][newX] == 0):
                maps[nowY][nowX] = max(0, maps[nowY][nowX] - 1)
            
            if(maps[newY][newX] > 0):
                Q.append((newX, newY))
                visited[newY][newX] = True


N, M = map(int, input().split(" "))

moveX = [1, 0, -1, 0]
moveY = [0, -1, 0, 1]
maps = []
result = True
year = 0
cnt = 0

for _ in range(N):
    maps.append(list(map(int , input().split(" "))))

while result:
    visited = [[False] * (M+1) for _ in range(N+1)]
    waters = [[0] * (M+1) for _ in range(N+1)]

    # 빙하 덩어리 개수 구하기
    for y in range(N):
        for x in range(M):
            if(visited[y][x] == False and maps[y][x] != 0):
                cnt +=1
                bfs(x, y)
                
                if(cnt >= 2):
                    break

    if(cnt >= 2):
        print(year)
        result = False
    else:
        isNotAble = all(maps[y][x] == 0 for y in range(N) for x in range(M))
        
        if(isNotAble):
            print(0)
            result = False
        else:
            cnt = 0
            year += 1

---

하하하 정답이다.

빙산이 2개 이상으로 나뉘어지거나 모든 빙산이 0이 될 때 까지 while문을 돌면 된다.

처음에는 아래처럼 모든 위치 탐색 로직을 3번이나 돌렸었는데,

올바른 출력은 나오지만 시간초과가 나서 실패했었다.

# 위치별 인접해있는 물 개수 구하기
    for y in range(N):
        for x in range(M):
            if(maps[y][x] != 0):
                getWaterLenth(x, y)
                
    # 각 빙산 값 줄이기
    for y in range(N):
        for x in range(M):
            if(maps[y][x] != 0):
                maps[y][x] = max(0, maps[y][x] - waters[y][x])
                
    # 빙하 덩어리 개수 구하기
    for y in range(N):
        for x in range(M):
            if(visited[y][x] == False and maps[y][x] != 0):
                cnt +=1
                bfs(x, y)
                
                if(cnt >= 2):
                    break

그래서 bfs 함수 안에서 다 할 수는 없나? 생각하다가 구현해봤는데 성공했다.

for i in range(4):
	newX = nowX + moveX[i]
    newY = nowY + moveY[i]

	if(newY >= N or newY < 0 or newX >= M or newX < 0):
		continue

	if(visited[newY][newX]):
    	continue

	if(maps[newY][newX] == 0):
    	maps[nowY][nowX] = max(0, maps[nowY][nowX] - 1)

	if(maps[newY][newX] > 0):
    	Q.append((newX, newY))
        visited[newY][newX] = True

이러면 방금 값이 1었다가 0이 된 빙산이어도

다음 빙산에서 해당 빙산을 0이라고 착각하여 값을 또 줄이면 어떡하지?

그러면 의도와 다르게 동작하지 않을까? 라는 생각이 있었지만

방문 여부 체크를 하기 때문에

원래 0이었던 빙산들에 한해서만 값을 줄여서 문제가 없다.