[백준/파이썬]2573 빙산

문제

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

2573번: 빙산

 

백준 2573번 빙산

 

 

빙산의 각 높이가 주어지고 매년 빙산기준으로 상하좌우에 있는 바다의 수만큼 빙산의 높이가 낮아진다.

 

그랬을 때, 하나의 빙산 덩어리가 2개 이상으로 나눠지는 년도를 찾는 문제다.

 

나는 이 문제를 BFS탐색을 두 번 써서 풀었다.

 

매년 녹는 빙산을 탐색하기 위해 한번, 빙산 덩어리가 몇개인지 탐색하기 위해 한번 이렇게 총 두 번 사용했다.

 

문제는 흔한 탐색 문제를 여러개 섞어둔 느낌

 

 

오답- 시간초과

    
def bfs() :
    global map_
    count = 0
    while queue :
        queue_len = len(queue)
        new_map = copy.deepcopy(map_)
        for _ in range(queue_len) :
            now_r, now_c = queue.popleft()
            minus_count = 0
            for j in range(4) :
                next_r, next_c = now_r + dx[j], now_c + dy[j]
                
                if next_r < 0 or next_c < 0 or next_r >= r or next_c >= c :
                    continue
                
                if map_[next_r][next_c] == 0 :
                    minus_count += 1
            if map_[now_r][now_c] - minus_count > 0 :
                queue.append((now_r, now_c))
                new_map[now_r][now_c] = map_[now_r][now_c] - minus_count
            else :
                new_map[now_r][now_c] = 0
        count += 1
        map_ = copy.deepcopy(new_map)
        visit = [[0 for _ in range(c)] for _ in range(r)]
        group_count = 0
        for ii in range(r) :
            #print(map_[ii])
            for jj in range(c) :
                if map_[ii][jj] != 0 and visit[ii][jj] == 0:
                    visit = find_group_bfs(ii, jj, visit)
                    group_count += 1
        if group_count > 1 :
            print(count)
            exit()

 

pypy로 제출시 정답 처리 됐지만, python으로 올리면 시간초과가 났던 코드다.

 

몇 가지 문제점이 있었는데,

1. 빙산 덩어리를 체크하기 위해 모든 인덱스를 탐색해서 시간 복잡도가 높았다.

• queue에 들어있는 것만 반복하면 됐었다.

2. 두 번째 deepcopy를 두 번이나 사용했다.

• 이게 매우 느리다고 한다..
• 만약 깊은 복사가 필요하다면 slicing을 이용한 깊은 복사가 더 빠르다고 하니 이거 쓰자
• 변경된 부분만 바꾸는 방식으로 deepcopy를 사용하지 않았다.

 

수정

def bfs() :
    global map_
    count = 0
    while queue :
        queue_len = len(queue)
        changes = {}
        for _ in range(queue_len) :
            now_r, now_c = queue.popleft()
            minus_count = 0
            for j in range(4) :
                next_r, next_c = now_r + dx[j], now_c + dy[j]
                
                if next_r < 0 or next_c < 0 or next_r >= r or next_c >= c :
                    continue
                
                if map_[next_r][next_c] == 0 :
                    minus_count += 1
            new_height = map_[now_r][now_c] - minus_count
            if new_height > 0 :
                queue.append((now_r, now_c))
                changes[(now_r, now_c)] = new_height
            else :
                changes[(now_r, now_c)] = 0
        
        for (i, j), new_height in changes.items():
            map_[i][j] = new_height
        count += 1
        visit = [[0 for _ in range(c)] for _ in range(r)]
        group_count = 0
        for ii, jj in queue :
            if visit[ii][jj] == 0:
                visit = find_group_bfs(ii, jj, visit)
                group_count += 1
        if group_count > 1 :
            print(count)
            exit()

 

이렇게 수정하고 나니 시간 초과 없이 통과 됐다.

 

정답

import sys
from collections import deque

def find_group_bfs(row, col, visit) :

    find_queue = deque()
    find_queue.append((row, col))
    while find_queue :
        now_r, now_c = find_queue.popleft()
        visit[now_r][now_c] = 1

        for i in range(4) :
            next_r, next_c = now_r + dx[i], now_c + dy[i]

            if next_r < 0 or next_c < 0 or next_r >= r or next_c >= c :
                continue
            if map_[next_r][next_c] != 0 and visit[next_r][next_c] == 0 :
                visit[next_r][next_c] = 1
                find_queue.append((next_r, next_c))
    return visit

    
def bfs() :
    global map_
    count = 0
    while queue :
        queue_len = len(queue)
        changes = {}
        for _ in range(queue_len) :
            now_r, now_c = queue.popleft()
            minus_count = 0
            for j in range(4) :
                next_r, next_c = now_r + dx[j], now_c + dy[j]
                
                if next_r < 0 or next_c < 0 or next_r >= r or next_c >= c :
                    continue
                
                if map_[next_r][next_c] == 0 :
                    minus_count += 1
            new_height = map_[now_r][now_c] - minus_count
            if new_height > 0 :
                queue.append((now_r, now_c))
                changes[(now_r, now_c)] = new_height
            else :
                changes[(now_r, now_c)] = 0
        
        for (i, j), new_height in changes.items():
            map_[i][j] = new_height
        count += 1
        visit = [[0 for _ in range(c)] for _ in range(r)]
        group_count = 0
        for ii, jj in queue :
            if visit[ii][jj] == 0:
                visit = find_group_bfs(ii, jj, visit)
                group_count += 1
        if group_count > 1 :
            print(count)
            exit()

        
input = sys.stdin.readline

r, c = map(int, input().split())

map_ = []

for i in range(r) :
    map_.append(list(map(int, input().split())))

dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
queue = deque()

for r_idx in range(r) :
    for c_idx in range(c) :
        if map_[r_idx][c_idx] != 0 :
            queue.append((r_idx, c_idx))

bfs()
print(0)