[python] boj 2573 빙산 : PyPy3이 아닌 Python3으로 돌려보자!!

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

2573번: 빙산

 

PyPy3으로는 어떻게든 돌아가는 로직이긴 한데 뭔가 오기가 생겨 Python3으로도 돌아가는 코드를 작성해보고 싶은 오기가 생겨서 작업하게 되었다.

 

일단 PyPy3으로 돌아가는 코드부터 알아보자.

 

1. PyPy3으로만 돌아가는 코드

기본 아이디어

1. 빙산이 몇 개 연결되어 있는지 계산해주는 함수를 만들어준다. (DFS 순회)
2. 빙산에 대한 정보를 ices 리스트에 넣어둔다.
3. 빙산 목록에서 하나씩 빼서 동서남북을 찾아보고 빙산을 녹인다.
4. 다만, 이번 턴에 얼음이 다 녹은 위치는 다른 빙산들에 영향을 주면 안 되기 때문에 0이 아닌 -1을 넣어준다.
5. 빙산이 다 녹지 않는다면 다음에 사용할 빙산 리스트를 만들어 차곡차곡 쌓아둔다.
6. 녹일 빙산을 다 녹이고 남아있는 빙산 리스트가 비어있다면 종료해준다.
7. 이번 턴에 녹일 얼음을 다 계산하면 -1로 입력된 빙산을 0으로 바꿔준다.
8. 남아있는 빙산 중에서 임의의 빙산을 선택하고 1번 과정에서 만들어준 함수를 사용하여 연결된 빙산의 개수를 구한다.
9. 연결된 빙산의 개수가 남아있는 빙산 리스트의 길이와 다르다면 빙산이 여러 조각이기 때문에 종료한다.

 

코드

import sys

sys.setrecursionlimit(20000)
readline = sys.stdin.readline
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

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

fields = [list(map(int, readline().split())) for _ in range(N)]
ices = []

# 빙산에 대한 정보를 ices 리스트에 넣어둔다.
for n in range(N):
    for m in range(M):
        if fields[n][m]:
            ices.append((n, m))

isFinished = False
year = 0

# 빙산이 몇 개 연결되어 있는지 계산해주는 함수
def get_connected_num(c_y, c_x, visited):
    cur_added = 0
    visited[c_y][c_x] = 1
    for c_d in range(4):
        n_y, n_x = c_y + dy[c_d], c_x + dx[c_d]

        if not visited[n_y][n_x] and fields[n_y][n_x]:
            cur_added += get_connected_num(n_y, n_x, visited)
    return cur_added + 1


while ices:
    year += 1
    # 이번 턴에 빙산이 다 녹는 위치를 담아두는 리스트
    zero_ices = []
    new_ices = []

    # 빙산 목록에서 하나씩 빼서 빙산을 녹이는 과정
    while ices:
        cur_y, cur_x = ices.pop()

        for d in range(4):
            new_y, new_x = cur_y + dy[d], cur_x + dx[d]
            if not fields[new_y][new_x]:
                fields[cur_y][cur_x] -= 1
                if fields[cur_y][cur_x] == 0:
                    # 이번 턴에 얼음이 다 녹은 위치는 다른 빙산들에 영향을 주면 안 되기 때문에 0이 아닌 -1을 표시해준다.
                    fields[cur_y][cur_x] = -1
                    zero_ices.append((cur_y, cur_x))
                    break
        else:
            new_ices.append((cur_y, cur_x))

    # 남은 빙산이 없다면 종료
    if len(new_ices) == 0:
        year = 0
        break

    # 이번 턴에 다 녹은 빙산의 위치 값을 0으로 바꿔줌
    for z_y, z_x in zero_ices:
        fields[z_y][z_x] = 0

    # 지금 빙산들이 다 연결되어 있는지 계산
    cur_num = get_connected_num(new_ices[0][0], new_ices[0][1], [[0 for _ in range(M)] for _ in range(N)])
    # 현재 남아 있는 빙산의 수와 임의의 위치에서 DFS를 순회한 결과가 다르다면 끝
    if cur_num != len(new_ices):
        break

    ices = new_ices

print(year)

 

 

2. Python3으로 돌아가는 코드

개선된 아이디어

1. 기존의 코드는 빙산을 녹이는 과정과 한 덩어리인지 확인하는 코드를 나눠 두 개의 반복문이 돌아가는 구조
2. 개선된 코드는 빙산을 녹이는 과정과 빙산이 몇 개 연결되어 있는지 같이 수행한다.
3. 함수는 연결된 빙산의 개수를 반환하고 이 값이 전체 빙산 개수와 다르다면 반복문을 멈추고 year를 출력한다.
4. 연결된 빙산 개수가 전체 빙산 개수와 같다면 -1로 처리된 모두 녹은 빙산을 0으로 반영하고 남아있는 빙산은 new_ices에 담아둔다.
5. new_ices의 길이가 0이라면 빙산이 나뉘기 전에 모두 녹았다는 뜻으로 0을 출력하고 멈춘다.
6. new_ices의 길이가 1이상이라면 ices에 반영하고 전체 while문을 다시 돌린다.

 

코드

import sys

sys.setrecursionlimit(20000)
readline = sys.stdin.readline
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

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

fields = [list(map(int, readline().split())) for _ in range(N)]
ices = []

# 빙산이 몇 개 연결되어 있는지 계산해주는 함수
# 몇 개 연결되어 있는지 계산하면서 녹인다.
def dfs(c_y, c_x, visited):
    cur_added = 0
    visited[c_y][c_x] = 1
    melt_num = 0
    for c_d in range(4):
        n_y, n_x = c_y + dy[c_d], c_x + dx[c_d]

        if visited[n_y][n_x]:
            continue

        if fields[n_y][n_x]:
            cur_added += dfs(n_y, n_x, visited)
        else:
            melt_num += 1
    else:
        if fields[c_y][c_x] - melt_num > 0:
            fields[c_y][c_x] -= melt_num
        else:
            fields[c_y][c_x] = -1

    return cur_added + 1

# 빙산에 대한 정보를 ices 리스트에 넣어둔다.
for n in range(N):
    for m in range(M):
        if fields[n][m]:
            ices.append((n, m))

isFinished = False
year = 0

while ices:
    new_ices = []

    # 지금 빙산들이 다 연결되어 있는지 계산
    cur_num = dfs(ices[0][0], ices[0][1], [[0 for _ in range(M)] for _ in range(N)])
    # 현재 남아 있는 빙산의 수와 임의의 위치에서 DFS를 순회한 결과가 다르다면 끝
    if cur_num != len(ices):
        break
    else:
        # 이번 턴에 다 녹은 빙산의 위치 값을 0으로 바꿔줌
        for i_y, i_x in ices:
            if fields[i_y][i_x] == -1:
                fields[i_y][i_x] = 0
            else:
                new_ices.append((i_y, i_x))

        if len(new_ices):
            year += 1
            ices = new_ices
        else:
            year = 0
            break

print(year)