[백준] [Python] 2468번 안전지대 - BFS

 

www.acmicpc.net/problem/2468

2468번: 안전 영역

Python

from collections import deque
n = int(input())

area = []
h = set()
for _ in range(n):
    area.append(list(map(int, input().split())))
    h = h | set(area[-1])
    

h =list(h)

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

cnt = 1
while h:
    k = h[-1]
    temp = 0
    visit = [[0]*n for _ in range(n)]
    q = deque()
    for i in range(n):
        for j in range(n):
            if visit[i][j] != 0 or area[i][j] <= k:
                continue
            visit[i][j]=1
            q.append([i,j])
            temp+=1

            while q:
                pos = q.popleft()

                for ii in range(4):
                    nx = pos[0]+dx[ii]
                    ny = pos[1]+dy[ii]
                    if 0<=nx<n and 0<=ny<n and visit[nx][ny]==0:
                        if area[nx][ny]>k:
                            visit[nx][ny] = visit[pos[0]][pos[1]]+1
                            q.append([nx,ny])
    #print(k,temp)
    cnt = max(cnt,temp)
    h.pop()
print(cnt)

 

 

짧은 풀이

set()의 합집합 기능을 이용하여 

모든 높이를 중복하지 않고 하나씩 받았음

하나씩 제외해보면서 최대값을 찾음