[Python]백준 #2468 안전영역 (DFS, BFS)

죽일거다 안전영역,,,,,

별것도 아닌걸로 내가 얼마나 개고생을 했는지 적어보도록 하자,,,,

알고리즘 문제란 정말 사소한걸로 실패 판정을 받는 잔인하고 섬세한 놈이다,,,,

✔️ 알고리즘

• 그래프 이론
• 브루트포스 알고리즘
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

결론부터 말하자면 이번 문제에서는 Queue 모듈과 문제에서 요구하는 바를 꼼꼼하게 구현하지 못했던 것이 미스테이크였다.

 

✔️ 접근방법

1. 입력 받은 지역 높이의 종류를 확인하여 해당 높이를 기준으로 기준보다 높으면 안전영역, 그렇지 않으면 침수영역으로 판단.

따라서 입력받은 지역의 높이를 저장한 2차원 리스트를 중복이 불가능한 자료형인 집합에 저장.

하지만 안전영역의 기준 높이가 1이상 일 수 있기 때문에 집합에 0을 추가.

2. 높이가 저장되어 있는 집합을 순회하면서 해당 높이를 기준으로 더 높은 지역들은 안전영역으로 판단하여 탐색.

bfs를 사용했고 잠기지 않는 첫 지역이 나오면 큐에 해당 지역이 삽입하면서 탐색이 시작됨.

그리고 while문도 시작되는데 while문은 큐에 삽입된 지역들에 인접한 지역들을 모두 탐색하여 잠기지 않은 한 영역을 탐색하면 끝남.

(즉 while문이 끝나면 안전영역 1개가 나오는 것)

큐에 첫 삽입이 이루어지는 순간에 area 변수를 +1 시켜 침수되지 않는 영역의 개수를 셈.

3. bfs를 사용했기 때문에 동서남북 리스트를 만들고 큐에서 뽑은 지역의 동서남북을 확인 (미로탐색과 동일)

4. 기준 높이에서 안전영역이 1개 이상이면 안전영역 리스트에 저장

5. 리스트에서 가장 큰 값을 출력

from collections import deque
import sys

input = sys.stdin.readline
N = int(input())
HeightArr = [list(map(int, input().split())) for _ in range(N)]

HeightSet = sum(HeightArr, [])
HeightSet = set(HeightSet)
HeightSet.add(0) # 안전영역 기준이 1이상인 경우 

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

for s in HeightSet:
    area = 0
    safeArr = [arr[:] for arr in HeightArr]  #deepcopy()는 슬라이싱에 비해 7배 가량 느리다

    for i in range(N):
        for j in range(N):
            que = deque()
            if (safeArr[i][j] > s):
                que.append([i, j])
                safeArr[i][j] = 0
                area += 1

            while(que):
                x, y = que.popleft()

                for n in range(4):
                    nx = x + dx[n]
                    ny = y + dy[n]

                    if (0 <= nx < N and 0 <= ny < N and safeArr[nx][ny] > s):
                        # 해당 좌표에 길이 존재하고 도착지점을 넘지 않는지 확인
                        que.append([nx, ny])
                        safeArr[nx][ny] = 0

    if (area > 0):
        areaList.append(area)


if (areaList):
    print(max(areaList))

 

✔️ 배운점/아쉬운점

1. 큐를 구현하기 위해 Queue 모듈을 사용했는데 이것때문에 계속 시간초과가 남. deque를 사용하니 문제 해결 

deque 는 각 명령을 O(1)으로 지원하는데에 반해, Queue 모듈은 멀티쓰레드 환경을 지원하기 때문에 더 느림

 

2. 입력 받은 지역 높이들을 집합에 저장해 놓고 기준 높이로 사용할 때, 가장 낮은 지역의 높이보다 하나 이상 작은 기준 높이를 집합에 추가하지 않았기 때문에 계속 실패했다. 예를 들어 2로만 이루어진 지역이 있을 때, 기준 높이인 2보다 큰 지역만 안전지역이라고 판단된 것이다. 하지만 기준 높이가 1인 경우 안전영역의 최대개수는 1이 될 수 있다. 

 

3. 탐색 과정에서 방문한 지역을 표시해야 했다. 이를 위해 입력받은 2차원 리스트를 복제하여 사용하려고 했는데 기존의 리스트를 변형시키지 않으려면 깊은 복사(deep copy)가 이뤄져야 했다. 그런데 나는 copy.deepcopy() 를 사용했었는데 이는 슬라이싱을 이용한 깊은복사보다 7배나 더 시간을 잡아먹는 방식이라는 것을 배움.

슬라이싱을 이용한 2차원 리스트의 깊은 복사는 [arr[:] for arr in 복사할2차원리스트]

1차원 리스트의 경우 복사할2차원리스트[:] 를 사용.