2468 안전영역

1. 문제

문제는 링크를 들어가면 볼 수 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

import sys
read =sys.stdin.readline

N = int(read())
graph = []

max_height = 0
for _ in range(N):
    temp = list(map(int,read().split()))
    graph.append(temp)
    max_height = max(max_height,max(temp))

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

from collections import deque

result_height = 0
for h in range(0,max_height):
    visited = [[-1] * N for _ in range(N)]

    q = deque()
    cnt = 0
    for y in range(N):
        for x in range(N):
            # 현재 위치가 침수됬는지 혹은 방문했었는지 확인
            if graph[y][x] <= h or visited[y][x] != -1 :
                continue
            else :
                q.append([y, x])
                visited[y][x] = 1
                # 아니라면 bfs 실행
                while q :
                    now = q.popleft()
                    for j in range(4):
                        ny = now[0] + dy[j]
                        nx = now[1] + dx[j]
                        # 정상 범주에 있고, 방문하지 않았어야함. 그리고 기둥이 침수되지 않아야함.
                        if 0<=ny<N and 0 <= nx < N and visited[ny][nx] == -1 and graph[ny][nx] > h :
                            visited[ny][nx] = cnt
                            q.append([ny,nx])

                cnt+=1
    result_height = max(result_height,cnt)
print(result_height)

3. 문제 풀이

이 문제는 bfs 기본 문제이다. 단지 약간의 조건이 추가된? 문제. 딱히 어렵진 않았지만, 이 문제부터 나는 visited graph를 적극적으로 사용하기로 맘먹었다. 많은 문제들이 결국 visited를 사용하지 않으면 문제가 발생했다.

최대 기둥의 높이를 구한 후, 0부터 max height - 1 까지 iteration을 돌면서 최대 안전 구역을 찾아야 한다. 이 때, 안전 구역을 탐색하는 것은 BFS를 사용하면 되므로 따로 설명은 하지 않겠다.