[BFS , DFS] 백준 빙산 2573번 with Python3

 

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

2573번: 빙산

문제

 

내 풀이 -시간초과-

# BOJ 2573 - 빙산 - 시간초과
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

# 상 우 하 좌
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]


def dfs_count(r, c):
    for m in range(4):
        nr = r + dr[m]
        nc = c + dc[m]
        if (0 <= nr < row) and (0 <= nc < col) and visit[nr][nc] == False and sea[nr][nc] != 0:
            visit[nr][nc] = True
            dfs_count(nr, nc)


def dfs_melt(r, c):
    count = 0
    height = sea[r][c]

    # 인접한 바다 수 세기
    for m in range(4):
        nr = r + dr[m]
        nc = c + dc[m]
        if (0 <= nr < row) and (0 <= nc < col) and sea[nr][nc] == 0 and land[nr][nc] == False:
            count += 1
    # 업데이트
    ini = height - count
    if ini > 0:
        sea[r][c] = height - count
    else:
        sea[r][c] = 0


# 입력
row, col = map(int, input().split())
sea = [list(map(int, input().split())) for _ in range(row)]


year = 0
while True:
    year += 1
    # 매해 방문 초기화
    visit = [[False]*col for _ in range(row)]

    # 빙산 덩이 개수 카운팅
    iceberg = 0
    for i in range(row):
        for j in range(col):
            if sea[i][j] != 0:
                if not visit[i][j]:
                    iceberg += 1
                    visit[i][j] = True
                    dfs_count(i, j)

    # 덩이가 2개 이상일 경우
    if iceberg > 1:
        print(year-1)
        exit()

    # 빙산 녹이기
    land = [[False]*col for _ in range(row)]
    for i in range(row):
        for j in range(col):
            if sea[i][j] != 0:
                land[i][j] = True
                dfs_melt(i, j)

    # 다 확인 하는지 체크
    check = 0
    for i in range(row):
        if any(sea[i]) == False:
            check += 1
        if check == row:
            print('0')
            exit()

해설

로직은 맞는거 같다. 하지만 시간초과로 실패. 답을 보고 내 답을 개선해봤다.

 

문제는 시간복잡도를 제외하고는 단순 구현에 가깝다. 이번에도 느끼지만 dfs 재귀 방식은 파이썬으로는 너무 느리다. 

 

 

정답 풀이

# BOJ 2573 - 빙산
from collections import deque
import copy
import sys
input = sys.stdin.readline

# 상 우 하 좌
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

# bfs 알고리즘으로 덩어리 개수 탐색
def bfs_count(i, j):
    q = deque()
    q.append([i, j])
    visit = [[0] * col for i in range(row)]
    visit[i][j] = 1

    while q:
        a, b = q.popleft()
        for k in range(4):
            nr = a + dr[k]
            nc = b + dc[k]
            if 0 <= nr < row and 0 <= nc < col and visit[nr][nc] == 0 and temp[nr][nc] != 0:
                temp[nr][nc] = 0
                visit[nr][nc] = 1
                q.append([nr, nc])

# dfs에 유사하게 주면 바다(0) 개수를 세고 리턴
def dfs_melt(r, c):
    count = 0
    # 인접한 바다 수 세기
    for m in range(4):
        nr = r + dr[m]
        nc = c + dc[m]
        if (0 <= nr < row) and (0 <= nc < col) and ts[nr][nc] == 0:
            count += 1
    return count

# 모두다 바다가 됬는지 체크하는 함수
def checkz():
    for i in range(row):
        for j in range(col):
            if sea[i][j] != 0:
                return False
    # 전부 0일 경우
    return True


# 입력
row, col = map(int, input().split())
sea = [list(map(int, input().split())) for _ in range(row)]


year = 1
while True:
    # 다 녹였는지 체크
    if checkz():
        print(0)
        break

    # 빙산 녹이기
    ts = copy.deepcopy(sea)
    for i in range(row):
        for j in range(col):
            if ts[i][j] != 0:
                temp = sea[i][j] - dfs_melt(i, j)
                sea[i][j] = temp if temp >= 0 else 0

    # 빙산 덩이 개수 카운팅
    temp = copy.deepcopy(sea)
    iceberg = 0
    for i in range(row):
        for j in range(col):
            if sea[i][j] != 0:
                if temp[i][j] != 0:
                    temp[i][j] = 0
                    bfs_count(i, j)
                    iceberg += 1

    # 빙산 덩어리의 개수 체크
    if iceberg > 1:
        print(year)
        break
    year += 1

출처:https://pacific-ocean.tistory.com/352

 

해석

실제로 로직은 거의 동일하다. 다만 copy 함수가 등장했는데 이게 시간 단축에 큰 의미가 있어보인다. 파악해보자.