[파이썬] 2468번 '안전 영역' 문제 풀이

[파이썬] 2468번 '안전 영역' 문제 풀이

※문제에 대한 정보는 하단의 링크(문제 출처) 참조

주어진 2차원 리스트에서의 최댓값은 가장 높은 지점이며 가장 낮은 지점부터 높은 지점까지 순회하면서 bfs나 dfs를 수행하여 방문처리를 해나가고 탐색을 마치면 count를 한 후, 다시 기준 높이보다 높은 지점에 대하여 다시 탐색을 수행합니다. 이렇게 구한 각각의 높이에 대한 count를 아래의 알고리즘을 통해 count 중 최댓값을 찾아냅니다.

def Max(Nums): Num=0 for i in Nums: if i >Num: Num=i return Num

2차원 리스트의 최댓값은 다음과 같은 코드를 작성하여 쉽게 구할 수 있습니다.

max(map(max,List))

문제 풀이

from collections import deque N=int(input()) Mat=[list(map(int,input().split())) for _ in range(N)] Max_Num=max(map(max,Mat)) Count=[0]*(Max_Num+1) def bfs(point,H): visited[point[0]][point[1]]=1 dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] queue = deque([point]) 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 visited[nx][ny]==0 and Mat[nx][ny]>H: visited[nx][ny] = 1 queue.append((nx, ny)) Max=0 for h in range(Max_Num): visited = [[0] * N for _ in range(N)] Count=0 for i in range(N): for j in range(N): if Mat[i][j]>h and visited[i][j]==0: bfs((i, j), h) Count+=1 if Max

dfs의 경우 아래 문제와 같은 유형의 문제이기 때문에 따로 코드를 작성하진 않았습니다.

https://lbdiaryl.tistory.com/188

문제 출처: https://www.acmicpc.net/problem/2468

from http://lbdiaryl.tistory.com/242 by ccl(A) rewrite - 2021-12-25 00:26:21