[BOJ] Python, Ruby 백준 빙산(2573)

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

 

BFS 탐색과 시뮬레이션 문제이다.

BFS로는 빙산이 몇개인지와 얼음이 주변 바닷물과 몇개나 접해있는를 카운트하는 역할을 하고

이중 for문으로 빙산이 어디 있는지와 얼음이 주변 바닷물에 맞닿아 있는 경우를 빼주는 방식으로 풀이 했다.

 

import sys
from collections import deque
input = sys.stdin.readline

N, M = map(int,input().split())
graph = [list(map(int,input().split())) for _ in range(N)]
time = 0
di,dj = [0,0,1,-1], [1,-1,0,0]

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

    while queue:
        ci,cj = queue.popleft()
        for i in range(4):
            ni,nj = ci + di[i], cj +dj[i]
            if 0 <= ni < N and 0 <= nj < M:
                if visited[ni][nj] == 0 and graph[ni][nj] > 0:
                    queue.append((ni,nj))
                    visited[ni][nj] = 1

                elif graph[ni][nj] == 0:
                    visited[ci][cj] += 1

while True:
    count = 0
    visited = [[0] * M for _ in range(N)]

    for i in range(N):
        for j in range(M):
            if visited[i][j] == 0 and graph[i][j] > 0:
                bfs(i,j)
                count += 1


    for i in range(N):
        for j in range(M):
            if visited[i][j] > 0:
                graph[i][j] -= (visited[i][j]-1)
                if graph[i][j] < 0:
                    graph[i][j] = 0


    if count > 1:
        print(time)
        break

    if count == 0:
        print(0)
        break

    time += 1

 

위는 빙산의 좌표를 이중for문으로 빙산의 위치를 찾은 후 갯수를 세고 다시금 이중 for문을 돌아 빙산을 녹인다.

 

 

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
time = 0
di, dj = [0, 0, 1, -1], [1, -1, 0, 0]

# 빙산 좌표를 저장하는 집합
icebergs = {(i, j) for i in range(N) for j in range(M) if graph[i][j] > 0}

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

    while queue:
        ci, cj = queue.popleft()
        for d in range(4):
            ni, nj = ci + di[d], cj + dj[d]
            if (0 <= ni < N and 0 <= nj < M and 
                (ni, nj) not in visited and graph[ni][nj] > 0):
                visited.add((ni, nj))
                queue.append((ni, nj))

while True:
    count = 0
    visited = set()
    new_icebergs = set()
    melt_list = []

    for i, j in icebergs:
        if (i, j) not in visited:
            bfs(i, j, visited)
            count += 1

        # 빙산 녹이는 과정 최적화
        melt = 0
        for d in range(4):
            ni, nj = i + di[d], j + dj[d]
            if 0 <= ni < N and 0 <= nj < M and graph[ni][nj] == 0:
                melt += 1

        if melt > 0:
            melt_list.append((i, j, melt))
        else:
            new_icebergs.add((i, j))

    # 빙산 녹이기
    for i, j, melt in melt_list:
        graph[i][j] -= melt
        if graph[i][j] > 0:
            new_icebergs.add((i, j))
        else:
            graph[i][j] = 0  # 음수 방지

    # 빙산 목록 갱신
    icebergs = new_icebergs

    if count > 1:
        print(time)
        break

    if not icebergs:
        print(0)
        break

    time += 1

하지만 위와 같이 변경해서, 겹치는 부분을 녹이기와 탐색을 동시에 함으로써 실행 속도를 단축시킬 수 있다.

 

회고,

파이썬으로는 시간초과가 났고, pypy3에서만 통과가 되어 실행시간 단축 방법 찾는 중에 위와 같은 풀이를 확인할 수 있었다. 아직 멀었담,,,