[Python] 백준 알고리즘 #2468 안전 영역 - bfs, brute force

문제

2468번: 안전 영역

 

풀이

해봐야 몇개 안되겠다 싶어서 브루트포스로 모든 상황을 다 돌리기로 하고,

그래도 반복의 횟수를 조금 줄이기 위해 하나도 물에 잠기지 않는 경우와, 모두 물에 잠기는 경우를 가지치기 했다.

그래서 인풋을 받으면서 값들의 최소와 최대를 minimum, maximum에 저장했다.

 

그 후, minimum부터 maximum까지 포문을 돌면서 인풋 값이 들어있는 field 배열을 복사해서 bfs를 했고,

안전영역의 갯수를 카운팅해줬다.

 

import sys
from collections import deque
import copy

N = int(input())
field = []
maximum = 0
minimum = 100
queue = deque()

dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
maxcount = 1

def bfs(j):
    while queue:
        now = queue.popleft()
        for i in range(4):
            ndr = now[0] + dr[i]
            ndc = now[1] + dc[i]

            if 0 <= ndr < N and 0 <= ndc < N and copied[ndr][ndc] > j:
                queue.append([ndr, ndc])
                copied[ndr][ndc] = -1


for i in range(N):
    ls = list(map(int, sys.stdin.readline().split(" ")))
    maximum = max(maximum, max(ls))
    minimum = min(minimum, min(ls))
    field.append(ls)


for j in range(minimum, maximum):
    count = 0

    copied = copy.deepcopy(field)

    for n in range(N):
        for m in range(N):
            if copied[n][m] > j:
                count += 1
                queue.append([n, m])
                copied[n][m] = -1
                bfs(j)
    maxcount = max(maxcount, count)


print(maxcount)

맞긴 했지만 메모리랑 시간을 보니 더 좋은 방법이 있을것같다.

 

 

메모

arr.copy()하면 얕은 복사(shallow copy)가 되기 때문에 원본이든 복사본이든 수정하면 다 같이 수정된다.

따라서 import copy를 해준 후 copy.deepcopy(arr) 이런식으로 복사해줘야 원본과는 별개인 복사본이 생긴다.