백준 2573 [빙산] 파이썬

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

 

생각보다 구현이 어려웠다.

python으로 돌리면 시간초과가 발생하였는데, pypy3는 통과하였다.

다른분의 코드를 보니 내 코드는 음... 막 짠 스파게티 코드다.

import sys
from collections import deque

# 방향 벡터 (상, 하, 좌, 우)
dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]

# 행(row), 열(col) 입력
row, col = map(int, sys.stdin.readline().split())

# 두 개의 빙산 필드 (field1, field2) 선언
field1 = [[0] * col for _ in range(row)]  # 현재 빙산 상태
field2 = [[0] * col for _ in range(row)]  # 녹은 후 빙산 상태

# 큐 선언 (빙산 위치를 저장)
q1 = deque([])
q2 = deque([])

# 큐 전환 플래그 (q1 사용 시 True, q2 사용 시 False)
q_toggle = True

# 정답 변수 (빙산이 분리되는 첫 번째 시간을 저장)
ans = 0

# 빙산이 분리되었는지 여부를 저장하는 변수
find_ans = False

# 빙산 데이터 입력받기
for i in range(row):
    s = list(map(int, sys.stdin.readline().split()))
    for j in range(col):
        if s[j] != 0:  # 빙산이 있는 경우
            q1.append([i, j])  # 빙산의 좌표를 큐에 저장
            field1[i][j] = s[j]  # field1에 빙산 높이 저장

# 시뮬레이션 시작
while True:
    ans += 1  # 1년이 지남
    visited = [[0] * col for _ in range(row)]  # 방문 여부 배열
    q = deque([])  # BFS 탐색용 큐
    cnt = 0  # 빙산 덩어리 개수
    del_pos = deque([])  # 녹아서 사라질 빙산 위치 저장

    if q_toggle:  # q1을 사용하는 경우
        while q1:
            r, c = q1.popleft()
            minus_cnt = 0  # 빙산이 녹을 양

            # 4방향 탐색하여 주변 바닷물 개수 확인
            for k in range(4):
                R, C = r + dr[k], c + dc[k]
                if 0 <= R < row and 0 <= C < col:
                    if field1[R][C] == 0:  # 바닷물인 경우
                        minus_cnt += 1

            # 녹은 후 빙산 높이가 0보다 크면 유지, 아니면 사라짐
            if field1[r][c] - minus_cnt > 0:
                field2[r][c] = field1[r][c] - minus_cnt  # field2에 새로운 빙산 높이 저장
                q2.append([r, c])  # 다음 탐색을 위해 큐에 추가
                visited[r][c] = -1  # 방문 여부 표시
            else:
                field2[r][c] = 0  # 빙산이 다 녹음
                del_pos.append([r, c])  # 사라질 위치 저장

        # 사라진 빙산을 field1에서 삭제
        while del_pos:
            r, c = del_pos.pop()
            field1[r][c] = 0

        q_toggle = not q_toggle  # 큐 전환

        # 빙산 덩어리 개수 체크
        for i in range(row):
            if find_ans:
                break
            for j in range(col):
                if cnt > 1:  # 덩어리가 2개 이상이면 종료
                    find_ans = True
                    break
                if visited[i][j] == -1:  # 새로운 빙산 덩어리 발견
                    cnt += 1
                    visited[i][j] = 1
                    q.append([i, j])

                    # BFS를 사용하여 같은 덩어리 탐색
                    while q:
                        r, c = q.popleft()
                        for k in range(4):
                            R, C = r + dr[k], c + dc[k]
                            if 0 <= R < row and 0 <= C < col and visited[R][C] == -1:
                                q.append([R, C])
                                visited[R][C] = 1

        if find_ans:
            break
        if not q2:  # 빙산이 모두 녹았을 경우
            find_ans = True
            ans = 0  # 정답을 0으로 설정
            break

    else:  # q2를 사용하는 경우 (위 로직과 동일)
        while q2:
            r, c = q2.popleft()
            minus_cnt = 0
            for k in range(4):
                R, C = r + dr[k], c + dc[k]
                if 0 <= R < row and 0 <= C < col:
                    if field2[R][C] == 0:
                        minus_cnt += 1

            if field2[r][c] - minus_cnt > 0:
                field1[r][c] = field2[r][c] - minus_cnt
                q1.append([r, c])
                visited[r][c] = -1
            else:
                field1[r][c] = 0
                del_pos.append([r, c])

        while del_pos:
            r, c = del_pos.pop()
            field2[r][c] = 0

        q_toggle = not q_toggle  # 큐 전환

        for i in range(row):
            if find_ans:
                break
            for j in range(col):
                if cnt > 1:
                    find_ans = True
                    break
                if visited[i][j] == -1:
                    cnt += 1
                    visited[i][j] = 1
                    q.append([i, j])
                    while q:
                        r, c = q.popleft()
                        for k in range(4):
                            R, C = r + dr[k], c + dc[k]
                            if 0 <= R < row and 0 <= C < col and visited[R][C] == -1:
                                q.append([R, C])
                                visited[R][C] = 1

        if find_ans:
            break
        if not q1:  # 빙산이 모두 녹았을 경우
            find_ans = True
            ans = 0
            break

# 결과 출력
print(ans)

주요내용은 빙산의 맵과 빙산높이를 담는 큐를 두개씩 생성하여, 한 번씩 번갈아가면서 빙산을 녹이고, 그 때 빙산이 분리되는지 확인한다.

 

 

 

다른 분의 코드를 첨부한다.

https://velog.io/@hygge/Python-%EB%B0%B1%EC%A4%80-2573-%EB%B9%99%EC%82%B0-BFS

[Python] 백준 2573 빙산 (BFS)

정말 깔끔하게 푸셨다...

1) BFS 함수를 생성

2) SET을 이용해 전체 빙산위치에서 삭제되는 위치를 깔끔하게 삭제

두가지 포인트에서 속도가 차이난거같다.

 

코드라인도 많이 차이난다..

import sys

from collections import deque

input = sys.stdin.readline

def bfs(x, y):

    q = deque([(x, y)])

    visited[x][y] = 1

    seaList = []

    while q:

        x, y = q.popleft()

        sea = 0

        for i in range(4):

            nx = x + dx[i]

            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m:

                if not graph[nx][ny]:

                    sea += 1

                elif graph[nx][ny] and not visited[nx][ny]:

                    q.append((nx, ny))

                    visited[nx][ny] = 1

        if sea > 0:

            seaList.append((x, y, sea))

    for x, y, sea in seaList:

        graph[x][y] = max(0, graph[x][y] - sea)

    return 1

n, m = map(int, input().split())

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

ice = []

for i in range(n):

    for j in range(m):

        if graph[i][j]:

            ice.append((i, j))

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

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

year = 0

while ice:

    visited = [[0] * m for _ in range(n)]

    delList = []

    group = 0

    for i, j in ice:

        if graph[i][j] and not visited[i][j]:

            group += bfs(i, j)

        if graph[i][j] == 0:

            delList.append((i, j))

    if group > 1:

        print(year)

        break

    ice = sorted(list(set(ice) - set(delList)))

    year += 1

if group < 2:

    print(0)