2573번 빙산(python3)

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

2573번: 빙산

bfs를 적용하면 된다.

이 문제의 핵심은 빙산을 깎을 때, 그 깎인 높이가 다른 빙산을 깎을 때 영향을 주면 안된다는 것이다.

나는 처음에 코드를 작성했을 때 배열의 깊은복사를 사용해서 작성했기 때문에 깊은 복사를 사용하지 않고 구현하는 방법을 찾아보았다.

from collections import deque
import copy
N, M = map(int, input().split())
data = []
for _ in range(N):
    data.append(list(map(int, input().split())))

not_one = []
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
visited = [[0] * M for _ in range(N)]
for i in range(N):
    for j in range(M):
        if data[i][j] != 0:
            not_one.append([i, j])

def bfs(a, b):
    queue = deque()
    queue.append([a, b])
    visited[a][b] = 1
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if data[nx][ny] != 0 and visited[nx][ny] == 0:
                    visited[nx][ny] = 1
                    queue.append([nx, ny])



ans = 0
temp_data = copy.deepcopy(data)
while True:
    for i in not_one:
        for j in range(4):
            nx = i[0] + dx[j]
            ny = i[1] + dy[j]
            if 0 <= nx < N and 0 <= ny < M:
                if temp_data[nx][ny] == 0:
                    if data[i[0]][i[1]] > 0:
                        data[i[0]][i[1]] -= 1
    temp_data = copy.deepcopy(data)
    count = 0
    flag = False
    visited = [[0] * M for _ in range(N)]
    for i in not_one:
        if data[i[0]][i[1]] != 0 and visited[i[0]][i[1]] == 0:
            flag = True
            bfs(i[0], i[1])
            count += 1
    if not flag:
        ans = 0
        break
    ans += 1
    if count > 1:
        break

print(ans)

위 코드는 내가 처음 작성한 코드다.

from collections import deque
N, M = map(int, input().split())
data = []
for _ in range(N):
    data.append(list(map(int, input().split())))

not_one = []
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
visited = [[0] * M for _ in range(N)]
for i in range(N):
    for j in range(M):
        if data[i][j] != 0:
            not_one.append([i, j])

def bfs(a, b):
    queue = deque()
    queue.append([a, b])
    visited[a][b] = 1
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if data[nx][ny] != 0 and visited[nx][ny] == 0:
                    visited[nx][ny] = 1
                    queue.append([nx, ny])
                if data[nx][ny] == 0 and data[x][y] != 0:
                    minus[x][y] += 1



ans = -1
temp_data = copy.deepcopy(data)
while True:
    minus = [[0] * M for _ in range(N)]
    visited = [[0] * M for _ in range(N)]
    count = 0
    flag = False

    for i in not_one:
        if data[i[0]][i[1]] != 0 and visited[i[0]][i[1]] == 0:
            bfs(i[0], i[1])
            count += 1
            flag = True
    if not flag:
        ans = 0
        break
    ans += 1
    if count > 1:
        break
    for i in range(N):
        for j in range(M):
            if data[i][j] - minus[i][j] < 0:
                data[i][j] = 0
            else:
                data[i][j] -= minus[i][j]

print(ans)

 

위 코드는 minus 리스트를 도입해서 다른 빙하에 영향을 주지 않으면서 깎는 것을 구현해냈다.