[BOJ] 2573번: 빙산 (BFS/DFS)

 

 

 

문제 링크

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

 

 

 

 

TIL

• BFS가 DFS보다 빠르다 !!!! >> 시간 초과날 때, BFS로 풀면 풀림
  • 실제로 이 문제의 경우, 똑같은 로직인데 BFS로 하면 통과, DFS로 하면 시간 초과 발생
  • DFS의 경우, pypy3로 제출하면 성공 (recursionlimit을 10**4로 해야 메모리초과 발생 안함)
• 동시성 잘 체크하기
  • 동시에 발생해야 하는 일인지 vs. 순차적으로 앞에서부터 발생해야하는 일인지
  • 이 문제의 경우, 1년이 지난 뒤 빙하가 녹을 때 동시에 녹아야했음!!
  • 따라서 melt라는 배열 따로 생성
• list끼리의 그냥 연산은 안됨 (ice -= melt 를 시도했으나 리스트끼리 뺄셈 실패)

 

• Tip
  • 음수값이 저장되지 않도록 하기 위해 쓸 수 있는 팁
    • ice[i][j] = max(0, ice[i][j] - melt[i][j]) # Ensure no negative values
    • 이러면 값이 음수라면 0이, 아니라면 계산된 값이 저장됨
  • 전체 배열이 0으로 되어있는지 확인하기 위해 쓸 수 있는  팁
    • if sum(sum(row) for row in grid) == 0:

 

[ 처음 코드 - DFS ] 시간초과

import sys
sys.setrecursionlimit(10**4)

n , m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
directions = [(0,1), (1,0), (-1,0), (0,-1)]

# 동시에 발생해야하는 일이기 때문에 순차적으로 하면 안됨!!!
def past_one_year(ice):
    melt = [[0 for _ in range(m)] for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if ice[i][j] > 0:
                for dy, dx in directions:
                    ny, nx = i+dy, j+dx
                    if 0<=ny<n and 0<=nx<m and ice[ny][nx] == 0 and ice[i][j] > 0:
                        melt[i][j] += 1
    # ice -= melt
    for i in range(n):
        for j in range(m):
            if ice[i][j] > 0:
                ice[i][j] = max(0, ice[i][j] - melt[i][j])  # Ensure no negative values

def dfs(i, j):
    visited[i][j] = True
    for dy, dx in directions:
        ny, nx = i+dy, j+dx
        if 0<=ny<n and 0<=nx<m and grid[ny][nx] > 0 and not visited[ny][nx]:
            visited[ny][nx]= True
            dfs(ny,nx)

def check_partition(ice):
    cnt = 0
    for i in range(n):
        for j in range(m):
            if ice[i][j] > 0 and not visited[i][j]:
                dfs(i,j)
                cnt += 1
                if cnt > 1:
                    return True
    return False

year = 0
while True:
    # impossible = True
    # for i in range(n):
    #     for j in range(m):
    #         if grid[i][j] > 0:
    #             impossible = False
    
    # if impossible:
    #     print("0")
    #     break

    if sum(sum(row) for row in grid) == 0:
        print("0")
        break

    past_one_year(grid)
    year += 1

    visited = [[False for _ in range(m)] for _ in range(n)]
    if check_partition(grid):
        print(year)
        break

 

 

 

 

Code

from collections import deque 

n , m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
directions = [(0,1), (1,0), (-1,0), (0,-1)]

# 동시에 발생해야하는 일이기 때문에 순차적으로 하면 안됨!!!
def past_one_year(ice):
    melt = [[0 for _ in range(m)] for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if ice[i][j] > 0:
                for dy, dx in directions:
                    ny, nx = i+dy, j+dx
                    if 0<=ny<n and 0<=nx<m and ice[ny][nx] == 0 and ice[i][j] > 0:
                        melt[i][j] += 1
    for i in range(n):
        for j in range(m):
            if ice[i][j] > 0:
                ice[i][j] = max(0, ice[i][j] - melt[i][j])  # Ensure no negative values

def bfs(i, j):
    visited[i][j] = True
    queue = deque()
    queue.append((i,j))

    while queue:
        cy, cx = queue.popleft()
        for dy, dx in directions:
            ny, nx = cy+dy, cx+dx
            if 0<=ny<n and 0<=nx<m and grid[ny][nx] > 0 and not visited[ny][nx]:
                visited[ny][nx]= True
                queue.append((ny,nx))

def check_partition(ice):
    cnt = 0
    for i in range(n):
        for j in range(m):
            if ice[i][j] > 0 and not visited[i][j]:
                bfs(i,j)
                cnt += 1
                if cnt > 1:
                    return True
    return False

year = 0
while True:

    if sum(sum(row) for row in grid) == 0:
        print("0")
        break

    past_one_year(grid)
    year += 1

    visited = [[False for _ in range(m)] for _ in range(n)]
    if check_partition(grid):
        print(year)
        break