[SW 정글] 백준 2573 - 빙산 (feat, python)

 

 

문제 설명

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

2573번: 빙산

 

 

문제 접근

 

1. 빙하 상하좌우에 바닷물이 몇 면에 접해잇는지 파악

2. 1년마다 빙하 녹이기

3. 빙하가 몇덩이인지 확인하기(2이상인지 0인지)

 

빙하가 1덩이라면 1, 2, 3을 계속 반복하긔

 

---

 

처음에는 빙하 하나씩 하나씩 차근차근 녹이려고 했다.

 

그러나

 

0 0 0 0 0

0 2 3 4 0

0 5 0 4 0

0 8 7 9 0

 

빙하가 있다고 하면

 

0 0 0 0 0

0 0 1 2 0

0 3 0 2 0

0 6 5 7 0

 

이 되어야하는데

 

0 0 0 0 0

0 0 0 1 0

0 2 0 2 0

0 6 5 7 0

이 되는 문제가 생겼다.

 

 

그래서 얕은 복사를 방지하기 위해 기존의 배열들을 deepcopy를 사용하여

 

저장해놧다가 한꺼번에 녹여주었다. 그렇게 답을 맞출 수 있었지만, 뭔가 찝찝했다.

 

그래서 우리 반의 기둥 형규형, 건희형❤️의 도움을 받아

 

나름 획기적인 방법으로 문제를 풀었다.

 

초기 visited를 False 설정하여 바닷물은 방문을 해도 visited을 고치지 않고

 

녹는 작업을 해준 빙하들만 visited를 True로 해서 빙하가 0이되더라도 방문하지 않게(visited가 TRUE니까) 구현을 하여

 

위 방법보다 더 간단하게 문제를 풀 수 있었다.

 

또한 시간복잡도, 메모리 부분에서도 더 우수한 성능을 보여줬다.

 

 

👍🏼👍🏼👍🏼👍🏼👍🏼👍🏼👍🏼

 

코드는 아래와 같다.

 

1. 내 코드(feat,형규형, 건희형) - 정답

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

N, M = map(int, input().split())

glaciers = [[int(x) for x in input().strip().split()] for _ in range(N)]

# 상하 좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def bfs(x, y):
    visited[x][y] = True
    dq = deque()
    dq.append((x, y))

    while dq:
        count = 0
        a, b = dq.popleft()
        for i in range(4):
            nx = a+dx[i]
            ny = b+dy[i]
            if 0 > nx or nx >= N or ny < 0 or ny >= M:
                continue
            if glaciers[nx][ny] == 0 and visited[nx][ny] == False:
                count += 1
            elif glaciers[nx][ny] > 0 and visited[nx][ny] == False:
                visited[nx][ny] = True
                dq.append((nx, ny))
        glaciers[a][b] = max(0, glaciers[a][b] - count)


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

    for i in range(N):
        for j in range(M):
            if glaciers[i][j] != 0 and visited[i][j] == False:
                bfs(i, j)
                lump += 1
    years += 1
    if lump >= 2:
        print(years-1)
        break
    elif lump == 0:
        print(0)
        break

 

 

2. 같이 녹는 코드 - 오답

import sys
from collections import deque
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

N, M = map(int, input().split())

glaciers = [[int(x) for x in input().strip().split()] for _ in range(N)]


def check(x, y):
    around = [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]
    count = 0
    for nx, ny in around:
        if glaciers[nx][ny] == 0:
            count += 1
    return count


def melt():
    for i in range(N):
        for j in range(M):
            if glaciers[i][j] == 0:
                continue
            else:
                meltN = check(i, j)
                counts[i][j] = meltN


def dfs(x, y):
    visieted[x][y] = True
    around = [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]
    for nx, ny in around:
        if glaciers[nx][ny] > 0 and not visieted[nx][ny]:
            dfs(nx, ny)


flag = False
years = 0
while True:
    visieted = [[False]*M for _ in range(N)]
    counts = [[0]*M for _ in range(N)]
    if flag:
        break
    count = 0
    melt()
    for i in range(N):
        for j in range(M):
            glaciers[i][j] -= counts[i][j]
            if glaciers[i][j] < 0:
                glaciers[i][j] = 0
    years += 1
    for i in range(N):
        for j in range(M):
            if glaciers[i][j] > 0 and visieted[i][j] == False:
                dfs(i, j)
                count += 1
    if count >= 2:
        flag = True
        print(years)
        break
    if count == 0:
        print(0)
        break

 

 

3. deep copy - 정답

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

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]


def count_ocean(x, y):
    count = 0

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < n and 0 <= ny < m and temp_graph[nx][ny] == 0:
            count += 1

    return count


def count_iceberg(start_x, start_y):
    q = deque()
    q.append((start_x, start_y))
    visited[start_x][start_y] = True

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] != 0 and not visited[nx][ny]:
                visited[nx][ny] = True
                q.append((nx, ny))


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

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

    flag = True
    for i in range(n):
        for j in range(m):
            if graph[i][j] != 0:
                flag = False

    if flag:
        print(0)
        break

    temp_graph = deepcopy(graph)
    for i in range(1, n - 1):
        for j in range(1, m - 1):
            if temp_graph[i][j] != 0:
                graph[i][j] = max(0, graph[i][j] - count_ocean(i, j))

    for i in range(1, n - 1):
        for j in range(1, m - 1):
            if not visited[i][j] and graph[i][j] != 0:
                count_iceberg(i, j)
                piece += 1

    if piece >= 2:
        print(answer)
        break

    answer += 1

 

 

 

 

bfs, dfs 문제를 처음 접했을 때는 뭐로 풀어야할지, 어떻게 풀어야할지 감이 안왔다.

 

그러나 열심히 많은 문제를 풀어보니, 대충 감도 잡히고 속도도 붙는 것 같아 뿌듯하다.

 

 

 

모두들 열코하자