[파이썬, Python] 백준 2468: 안전 영역

문제

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

2468번: 안전 영역

코드

import copy
import sys
sys.setrecursionlimit(10**6)

n = int(input())
land = list(list(map(int, input().split())) for i in range(n))
ans = []

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

def dfs(x, y):
    new_land[x][y] = 0
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
    
        if 0 <= nx < n and 0 <= ny < n and new_land[nx][ny] >= 1:
            dfs(nx, ny)
        
for water in range(max(map(max, land))+1):
    new_land = copy.deepcopy(land)
    cnt = 0
    
    for i in range(n):
        for j in range(n):
            if new_land[i][j] <= water:
                new_land[i][j] = 0

    for i in range(n):
        for j in range(n):
            if new_land[i][j] >= 1:
                dfs(i, j)
                cnt += 1

    ans.append(cnt)
    
print(max(ans))

설명

dfs로 풀어야 한다는 접근 자체는 금방 했지만 중간중간 디테일에서 걸리는 게 많았던 문제였다.

우선 입력값을 받아주고 답을 담아둘 ans를 만들어둔다.
그리고 4방향 dfs이므로 4방향을 지정해준다.

dfs는 land의 복사본을 만들어서 돌릴 예정이므로 방문한 땅을 0으로 바꿔서 처리했다.

땅의 최대 범위 사이와 1 이상인 경우(땅이 잠기지 않은 경우)만
추가로 dfs를 수행한다(땅이 연결되어 있는 경우).

그리고 물의 범위를 지정해야 하는데 2차원 배열의 max 값을 찾는 방법을 활용했다.
처음에 단순하게 max(max(land))로 설정했다가 에러를 만났다.
예를 들어 땅이 3인 경우
3 3 6
1 1 1
1 1 9
와 같은 땅인 경우 max(land)가 3 3 6이 되어 max(max(land))는 6이 되어버려 max 값에 에러가 난다.

이를 방지하기 위해 각 열의 max 값에서 max를 찾는다.

그리고 땅을 복사하는 과정에서도 에러가 있었다.
땅을 그냥 new_land = land로 복사하게 되면
메모리값에 영향을 주어 2번째 루프부터 기존 land의 이용이 불가능했다.

이를 해결하기 위해 copy의 deepcopy를 사용하여 해결했다.

그 이후에는 물의 깊이에 맞춰
물보다 낮은 땅은 0으로 바꿔주어 방문하지 않게 하고
dfs를 수행했다.

이 결괏값들을 and 리스트에 담아두고
모든 수행이 끝난 후 and의 최댓값을 출력한다.