[백준] 2573 - 빙산 BFS (Python3)

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

 

바다 0과 각 빙산의 높이(1 이상의 정수)가 담긴 이차원 배열이 있다.

매년 각 빙산은 주변에 둘러쌓인 바다의 면 수 만큼 높이가 줄어든다.

빙산이 2개 이상의 조각으로 분리될 때까지 걸리는 년수?

 

비슷한 문제는 백준에 '그림' 문제가 있다

연결된 1의 개수를 세어서 그림 위에 색칠된 영역 덩어리가 몇 개인지 세는 것

거기에서 매년 높이가 줄어드는 로직만 추가됨

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

그림 문제와 같이 우선 각 덩어리를 세는 함수를 추가한다

 

1. 각 빙산의 덩어리 수를 구하는 함수

이중 for문으로 입력 배열을 탐새하면서, 방문한 적이 없고, 빙산인 경우(바다가 아닌 경우)

해당 점을 시작으로 빙산을 탐색한다

 

이를 반복하면 시작점으로부터 연결되어 있는 조각만 탐색하고 bfs문이 끝남

그래서 조각 개수를 탐색할 수 있다

from collections import deque
n,m = map(int, input().split())

arr =[list(map(int,input().split())) for _ in range(n)]
dx=[0,0,1,-1]
dy=[1,-1,0,0]
def bfs(y,x,visited):
    q = deque()
    q.append((y,x))
    visited[y][x] = 1

    while q:
        cur = q.popleft()
        for i in range(4):
            x_ = cur[1]+dx[i]
            y_ = cur[0]+dy[i]
            if 0<=x_<m and 0<=y_<n and visited[y_][x_]==0 and arr[y_][x_]>0:
                visited[y_][x_]=1
                q.append((y_,x_))


while True:
    visited = [[0 for _ in range(m)] for _ in range(n)]
    count = 0
    for i in range(n):
        for j in range(m):
            if arr[i][j] >0 and visited[i][j]==0:
                bfs(i,j,visited)
                count+=1

 

 

 

2. 매년 빙산의 높이를 깎는 함수

덩어리 개수가 0이거나 2 이상이 아니면 종료 조건이 아님

melt 함수를 실행시켜서 빙산 높이를 깎는다

 

빙산 덩어리가 1개라는 뜻이기 때문에 bfs가 한 번에 끝난다고 가정해 된다(visited 없어도 ㄱㅊ)

각 점의 상하좌우에 있는 0의 개수를 구해서 빼준다

0 이하 값이 발생하지 않도록 max 함수를 써서 음수 값이 나올 경우엔 0으로 대체한다. (바다 or 빙산으로만 관리하기 위해)

 

melt함수 실행 후에는 년수 year를 1 증가시킨다

def melt():
    temp = [[0 for _ in range(m)] for _ in range(n)]
    for y in range(n):
        for x in range(m):
            if arr[y][x]>0:
                cnt=0
                for i in range(4):
                    x_ = x+dx[i]
                    y_ = y+dy[i]
                    # 0 개수 세서 그만큼 빼주기
                    # 음수가 되지 않게 max 사용
                    if 0<=x_<m and 0<=y_<n and arr[y_][x_]==0:
                        cnt+=1
                temp[y][x] = max(0,arr[y][x]-cnt)
    return temp

year=0

while True:
    visited = [[0 for _ in range(m)] for _ in range(n)]
    count = 0
    for i in range(n):
        for j in range(m):
            if arr[i][j] >0 and visited[i][j]==0:
                bfs(i,j,visited)
                count+=1
    if count==0:
        year=0
        break
    if count>=2:
        break
    arr=melt()
    year+=1

    
print(year)

 

 

 

 

 

 

from collections import deque
n,m = map(int, input().split())

arr =[list(map(int,input().split())) for _ in range(n)]
dx=[0,0,1,-1]
dy=[1,-1,0,0]
def bfs(y,x,visited):
    q = deque()
    q.append((y,x))
    visited[y][x] = 1

    while q:
        cur = q.popleft()
        for i in range(4):
            x_ = cur[1]+dx[i]
            y_ = cur[0]+dy[i]
            if 0<=x_<m and 0<=y_<n and visited[y_][x_]==0 and arr[y_][x_]>0:
                visited[y_][x_]=1
                q.append((y_,x_))

def melt():
    temp = [[0 for _ in range(m)] for _ in range(n)]
    for y in range(n):
        for x in range(m):
            if arr[y][x]>0:
                cnt=0
                for i in range(4):
                    x_ = x+dx[i]
                    y_ = y+dy[i]
                    # 0 개수 세서 그만큼 빼주기
                    # 음수가 되지 않게 max 사용
                    if 0<=x_<m and 0<=y_<n and arr[y_][x_]==0:
                        cnt+=1
                temp[y][x] = max(0,arr[y][x]-cnt)
    return temp

year=0

while True:
    visited = [[0 for _ in range(m)] for _ in range(n)]
    count = 0
    for i in range(n):
        for j in range(m):
            if arr[i][j] >0 and visited[i][j]==0:
                bfs(i,j,visited)
                count+=1
    if count==0:
        year=0
        break
    if count>=2:
        break
    arr=melt()
    year+=1

    
print(year)

 

 

while문 내부에서 덩어리 세기+년수 증가시키며 빙산 높이 깎기를 반복하다보면

count가 2 이상인(덩어리가 분리되는) 지점이 나오는데, 그때 break문으로 끊어주고 year print하면 끝

 

근데 이 코드는 pypy3으로 돌려야먄 시간초과가 안뜬다

 

gpt가 최적화 해준 코드는 아래와 같다

 

from collections import deque

n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]

def bfs(y, x, visited):
    q = deque()
    q.append((y, x))
    visited[y][x] = 1
    while q:
        cy, cx = q.popleft()
        for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            ny, nx = cy + dy, cx + dx
            if 0 <= ny < n and 0 <= nx < m and not visited[ny][nx] and arr[ny][nx] > 0:
                visited[ny][nx] = 1
                q.append((ny, nx))

def melt():
    temp = [[0] * m for _ in range(n)]
    for y in range(n):
        for x in range(m):
            if arr[y][x] > 0:
                count = 0
                for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    ny, nx = y + dy, x + dx
                    if 0 <= ny < n and 0 <= nx < m and arr[ny][nx] == 0:
                        count += 1
                temp[y][x] = max(0, arr[y][x] - count)
    return temp

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

    for i in range(n):
        for j in range(m):
            if arr[i][j] > 0 and not visited[i][j]:
                bfs(i, j, visited)
                cnt += 1

    if cnt == 0:  # All icebergs melted
        year = 0
        break
    if cnt >= 2:  # Icebergs are separated
        break

    arr = melt()
    year += 1

print(year)

 

아마 이중 for문을 정직하게 안돌리고 for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]: 이렇게 한줄처리하는 부분이 관건인 것 같다