[백준] 2573번 빙산 (파이썬)

난이도 : GOLD IV

문제링크 : https://www.acmicpc.net/problem/2573

문제해결 아이디어

• BFS를 사용해서 조건을 만족하는 빡구현 이였다. (내가 느끼기엔)

소스코드

import copy
from collections import deque
import sys

input = sys.stdin.readline

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

graph = []

for _ in range(n):
    graph.append(list(map(int, input().split())))

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


def bfs(x, y):  # 2등분 됐는지 확인하는 로직
    visited = copy.deepcopy(graph) 

    for i in range(n):
        for j in range(m):
            if visited[i][j] == 0:
                visited[i][j] = True
            else:
                visited[i][j] = False

    q = deque([(x, y)])
    visited[i][j] = 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 not visited[nx][ny]:
                q.append((nx, ny))
                visited[nx][ny] = True

    for i in range(n):
        for j in range(m):
            if not visited[i][j]:
                return True  # 이등분 됨

    return False  # 이등분 안됨


def melt():
    iceberg = [[0] * m for _ in range(n)]

    for i in range(n):
        for j in range(m):
            if graph[i][j]:
                h = graph[i][j]
                for k in range(4):
                    nx = i + dx[k]
                    ny = j + dy[k]

                    if graph[nx][ny] == 0:
                        h -= 1

                if h <= 0:
                    iceberg[i][j] = 0
                else:
                    iceberg[i][j] = h

    return iceberg


year = 1

while True:
    graph = melt()
    secBreak = True
    for i in range(n):
        for j in range(m):
            if graph[i][j]:
                if bfs(i, j):
                    print(year)
                    exit()
                else:
                    year += 1
                    secBreak = False
                    break

        if not secBreak:
            break
    else:
        print(0)
        exit()