[백준_2573] 빙산 python

첫째로 실패했던 것은,

is_divided()함수에서,

빙산이 있고, 방문한 적 없는 빙산을 체크해야 하는데,

두 번째 조건을 빼 놓고 생각했다는 것,

 

두 번째로 실패했던 것은,

최대 리커전 횟수를 늘려 주지 않았다는 것.

이외에는 재밌게 푼 문제같다.

# 입력

# n, m 입력
n, m = map(int, input().split())

# north_pole 입력
north_pole = [
    list(map(int, input().split()))
    for _ in range(n)
]

# 함수들

# is_ocean(x, y)
def is_ocean(x, y):
    return not north_pole[x][y]

# check_pow(x, y)
def check_pow(x, y):
    # pow
    pow = 0

    # dxs, dys
    dxs, dys = [-1, 1, 0, 0], [0, 0, 1, -1]
    for dx, dy in zip(dxs, dys):
        # 주변 위치
        nx, ny = x + dx, y + dy
        # 바다이면
        if is_ocean(nx, ny):
            # pow 올려주기
            pow += 1
    
    # pow 반환
    return pow

# simulate()
def simulate():
    
    global north_pole

    # 위치와 녹을 정도를 기록해 줄 리스트
    pos_and_pow = []

    # 북극 돌면서
    for i in range(n):
        for j in range(m):
            # 빙산을 만나면
            if north_pole[i][j]:
                # 좌표와 녹을 정도를 측정하여 리스트에 기록
                pos_and_pow.append((i, j, check_pow(i, j)))
    
    # 녹여주기
    for x, y, p in pos_and_pow:
        north_pole[x][y] -= p
    
    # 녹이고 나서 음수가 된 애들 0으로 돌려주기
    for i in range(n):
        for j in range(m):
            if north_pole[i][j] < 0:
                north_pole[i][j] = 0

# in_range(x, y)
def in_range(x, y):
    return 0 <= x and x < n and 0 <= y and y < m

# check(x, y)
def check(x, y):
    # 범위 내에 있고, 방문한 적 없고, 바다가 아니면 가능
    return in_range(x, y) and not visited[x][y] and north_pole[x][y]

# dfs(x, y)
def dfs(x, y):
    # dxs, dys
    dxs, dys = [-1, 1, 0, 0], [0, 0, -1, 1]
    for dx, dy in zip(dxs, dys):
        # 다음 위치
        nx, ny = x + dx, y + dy
        # 다음 위치가 갈 수 있으면,
        if check(nx, ny):
            # 방문 처리 해 주고,
            visited[nx][ny] = 1
            # dfs호출
            dfs(nx, ny)

# is_divided()
def is_divided():
    
    # area -> 이어져 있는 땅 개수
    area = 0
    
    # 북극을 돌면서
    for i in range(n):
        for j in range(m):
            # 빙산이 있고, 방문한 적 없는 빙산이면
            if north_pole[i][j] and not visited[i][j]:
                # area 개수 올려주고
                area += 1
                # 방문 처리 해주고
                visited[i][j] = 1
                # dfs 호출
                dfs(i, j)
    
    # area가 2 이상이면
    if area >= 2:
        # 나뉘어져 있음
        return True
    
    # 아니면 실패
    return False

# all_melted()
def all_melted():
    # 북극을 돌면서
    for i in range(n):
        for j in range(m):
            # 빙산을 발견하면
            if north_pole[i][j]:
                # 실패
                return False
    # 다 돌았는데 빙산이 없으면 성공
    return True

# 설계

# 최대 리커젼 횟수 올려주기
import sys
sys.setrecursionlimit(15000)

# ans
ans = 0
while True:

    # visited (매번 초기화)
    visited = [
        [0] * m
        for _ in range(n)
    ]

    # 만약 다 녹았는데 안나눠졌으면,
    if all_melted():
        # 0 출력 후
        print(0)
        # 반복문 종료
        break

    # 만약 두 개로 나뉘어졌으면
    elif is_divided():
        # 정답 출력해주고,
        print(ans)
        # 반복문 종료
        break

    # 아직 안나눠졌으면,
    else:
        # 시뮬레이션 돌려주고,
        simulate()
        # ans 하나 올려줌
        ans += 1