파이썬 백준 2468 안전 영역

import sys sys.setrecursionlimit(100000) input = sys.stdin.readline maxheight = 0 minheight = 101 n = int(input()) originH = [] for i in range(n) :     row = list(map(int, input().split()))     maxheight = max(maxheight, max(row))     minheight = min(minheight, min(row))     originH.append(row) dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] def BFS(X, Y) :     que = [[X, Y]]     while que :         a, b = que[0][0], que[0][1]         del que[0]         for i in range(4) :             x = a + dx[i]             y = b + dy[i]             if footprint[x][y] > 0 :                 footprint[x][y] = 0                 que.append([x, y]) H = [[0]*(n+2)]*(n+2) maxc = 0 for i in range(n) :     H[i+1] = [0] + originH[i] + [0] for h in range(minheight - 1, maxheight) :     footprint = [[1]*(n+2) for i in range(n+2)]     count = 0     for i in range(n+2) :         for j in range(n+2) :             if H[i][j] <= h :                 footprint[i][j] = 0     for i in range(n+2) :         for j in range(n+2) :             if footprint[i][j] == 1 :                 footprint[i][j] = 0                 BFS(i, j)                 count = count + 1     maxc = max(maxc, count) print(maxc)

지금 있는 곳이 발자국이 안찍힌 곳이면 발자국을 찍고 함수 BFS를 시작한다.

BFS를 시작하면 처음에는 함수에 입력한 첫 좌표 하나만 que(queue)의 원소로 들어있고, 이 que에 대해 while문을 돌린다.

만약 BFS가 돌아가는 위치의 상하좌우 근접위치에 발자국이 안찍힌 곳이 있다면 발자국을 찍고, 그 위치도 que에 넣는다.

while문 안에서 지금 돌아가는 que의 원소를 del했으니 각 원소는 while 안의 구문을 실행시키고 자기 할일을 다 하면 que에서 사라진다. 그리고 그 '할일'에 의해 que에 새로 추가된 원소는 다시 while문의 동력원이 된다.

언젠가 더이상 발자국이 안찍힌 곳이 없다면 while 안의 구문이 헛돌면서 que의 원소들을 날릴 것이고, que에 더이상 원소가 없어지면 False가 되면서 while문이 끝난다.

 

새로 추가된 할일을 DFS의 for if문처럼 우선적으로 끼워넣는게 아니라, 할 일 list인 queue의 맨 끝에 추가하는 것. 이게 BFS의 원리인 것 같다.

 

아무튼 이렇게 하나의 while문이 끝나면 BFS가 시작된 위치와 인접한 모든 곳에 발자국이 찍히고, count가 1 늘어난다.

이걸 행렬의 모든 위치에 대해 찔러보면 발자국이 찍힌 영역이 총 몇곳인지를 셀 수 있다.

 

이것을 모든 물높이 h에 대해 반복해서 max값을 구하면 끝

dxdy를 이용한 주변 판정에서 -1열이나 n+1열같은 range 바깥을 건드려 에러가 나는걸 막기 위해 상하좌우 높이 0짜리 커버를 씌웠고, 결과적으로 H의 size가 n+2이 되었다.

while문 안의 a+dx, b+dy에 대해서만 행렬 바깥으로 나가진 않았는지 확인하는 if문을 넣는 것이 행렬 전체를 n+2 size로 키우는 것보단 자원을 덜 쓰겠지만, 처음 써보는 BFS while문 안을 복잡하게 만들긴 힘들어서 사이즈를 키우고 while문을 간단하게 만들었다.