[백준][python]2468 안전영역

문제

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

소스코드

import sys
from collections import deque

if __name__ == "__main__":
    n = int(input())
    arr = [list(map(int,input().split())) for _ in range(n)]
    res = 0
    
    maxnum = max(max(arr))
    
    def check(l):
        tmpres = 0
        visited = [[0] * n for _ in range(n)] 

        dx = [1,-1,0,0]
        dy = [0,0,1,-1]
        q = deque()
        for i in range(n):
            for j in range(n):
                if arr[i][j] > l and not visited[i][j]:
                    q.append([i,j])
                    visited[i][j] = 1
                    tmpres +=1
                    while q:
                        x,y = q.popleft()
                        for k in range(4):
                            xx = x + dx[k]
                            yy = y + dy[k]
                            if 0<=xx<n and 0<=yy<n and arr[xx][yy] > l and not visited[xx][yy]:
                                q.append([xx,yy])
                                visited[xx][yy] = 1
        return tmpres

    for i in range(maxnum):
        res = max(check(i),res)

    print(res)

후기

1. 처음에 copy.deepcopy를 사용해서 arr를 매번 복사해서 침수 여부를 체크했다. 그랬더니 메모리 초과가 났다. 그래서 visited 배열을 생성하여 함께 체크하는 방식으로 변경했더니 메모리 초과 문제를 해결할 수 있었다.

-> 혹시 몰라서 slicing으로 deepcopy를 했지만 역시 메모리 초과;

 

2. bfs 체크하는 로직을 Check 함수로 빼는거랑 빼지않는거랑 시간차이가 3배정도 난다. 

1) Check 함수로 빼준 경우

2) 빼주지 않은 경우

 

3.문제에 하나도 잠기지 않은 경우가 존재한다라고 했다.  이는 잠기거나 0 잠기지 않은 경우 1 2가지 경우가 있는 것이므로 무조건 1이 가장 작은 정답이다.