[ 파이썬(python) ] 백준 2468 - 안전 영역

📌 백준 2468 - 안전 영역

문제 설명

---

💡 나의 풀이

문제를 이해하는 데는 어렵지 않았지만, 구현하는데 나름대로 어려웠던 문제였다. 아직 구현 실력이 뛰어나지 않아서 그런 것 같다.

 

N의 최대 범위가 100 * 100이어서 시간 복잡도가 O(N^3)이어도 시간초과가 나지 않을 것이라고 판단했는데, 같은 지역에서 내리는 비의 양에 따른 모든 경우를 조사해야 하기 때문에 이중 반복문에서 삼중 반복문으로 늘어났다.

 

모든 높이를 조사할때는 입력값 중 가장 작은 값부터 가장 큰 값을 범위로 잡았다. 여기서 pythonic코드를 배웠는데 2차원의 배열에서 min, max값을 찾을 때 map함수를 사용하면 간단하게 출력할 수 있다. 반복문 안에서 가장 큰 값의 범위를 설정할 때는 +1을 해주자 아니면 오답 판정 난다.

728x90

그리고 BFS함수에서 변수를 x, y 좌표 외에도 value를 하나 더 줬는데, 구해야 하는 높이가 반복문마다 바뀌므로 변수로 같이 전달해줬다.

 

또, 핵심 포인트는 BFS를 통해 반복문을 한번 돌고 나올 때마다 visited와 cnt를 초기화해줘야 한다. 이걸 안 해줘서 시간이 오래 걸렸던 것 같다.

 

첫 입력 좌표를 방문했다고 선언했어야 하는데 graph를 방문했다고 설정하니까 출력이 제대로 안 나왔다. 이건 파이참이 고장 난 거야!라고 생각했지만 사실  (내 머리가 고장 났었다.)

 

 

테스트 케이스 한 개를 예로 들면, 높이가 4 이하인 지점이 모두 잠겼을 때의 안전한 영역을 구할 때의 순서는 다음과 같다.

 

1. BFS 함수 구현(생략)
2. 모든 좌표에 대해 검사한다.(조건: 구하려고 하는 높이가 graph[i][j] 이상이고 visited에 방문한 적이 없을 때)
3. BFS 함수를 실행한 횟수 누적
4. 안전한 영역의 최댓값 갱신

 

코드 제출할 때 python3, pypy 각각 제출했는데, 메모리와 시간이 다르게 계산됐다.

 

 

from collections import deque
import sys
input = sys.stdin.readline

def bfs(x, y, safe_area):    # BFS implementation
    queue = deque()
    queue.append((x, y))
    visited[x][y] = 1	# visited mark

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

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

            if 0 <= nx < N and 0 <= ny < N:
                if graph[nx][ny] >= safe_area and visited[nx][ny] == 0:    
                    visited[nx][ny] = 1
                    queue.append((nx, ny))

N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
graph_min = min(map(min, graph))    # min_height
graph_max = max(map(max, graph))    # max_height
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

max_safe_area = graph_min   # init min_value
for safe_area in range(graph_min, graph_max+1):
    visited = [[0] * N for _ in range(N)]
    temp = 0
    for i in range(N):
        for j in range(N):
            if graph[i][j] >= safe_area and visited[i][j] == 0:
                bfs(i, j, safe_area)
                temp += 1
    if temp > max_safe_area:    # update safe_zone count
        max_safe_area = temp
print(max_safe_area)