[코테] BFS - 안전영역[백준 / 2468]

문제

출처: 백준 - 안전영역 : 2468번

풀이:

BFS 넓이 우선탐색 문제다.
물에 잠기지 않은 안정영역을 찾는 BFS 문제의 조건에서 높이 h에 따른 영역의 개수까지 구해야 하는 조건이 추가되었다. 안전영역의 높이는 1부터 주어지므로 높이는 안전영역 1이 잠기지 않는 구간인 0부터 시작해서 100사이의 높이를 1씩 높여가며 BFS탐색으로 각각 탐색한 후 가장 많은 안전영역의 개수를 반환하면 된다. 100까지 진행하지만 최대 높이가 예시와 같이 9라면 10부터는 탐색하지 않도록 조건을 추가한다.

1. 먼저 n을 받고 안정영역의 부분도 n길이 만큼의 2차원 배열 board를 생성한다.
2. 높이가 0부터 시작하여 반복문을 진행할 때, 안정영역인 부분을 체크하고 재방문하지 않도록 높이가 변경될 때마다 방문 체크를 할 수 있는 안전영역과 같은 크기의 2차원 배열을 생성한다. 그리고 안정영역 발견 시 상하좌우로 탐색할 수 있도록 한다.
3. 높이마다 달라지는 안전영역의 값 중 max값을 담을 수 있도록 한다.
4. 안정영역의 높이가 모두 물에 잠기게 되는 최대 높이를 가지게 되면 안전영역은 0이 되므로 거기에서 반복문을 중단하도록 한다.

코드:

from collections import deque

n = int(input()) # n을 받고
board = [list(map(int, input().split())) for _ in range(n)] # n크기의 2차원 배열을 받아 생성
dx = [0, 1, 0, -1] # 상하좌우 탐색할 수 있도록 방향 설정
dy = [-1, 0, 1, 0]
dQ = deque() # 안전영역이 발견되면 큐에 담을 수 있도록 한다.
result = 0 # 안전영역이 가장 많은 max값을 담을 수 있는 변수 지정

for h in range(100): # 0부터 100까지 높이 마다 탐색을 한다.
    ch = [[0] * n for _ in range(n)] # 방문 체크를 할 2차원 배열을 높이마다 생성
    cnt = 0 # 안전영역의 개수를 담을 변수
    for i in range(n):
        for j in range(n):
            if board[i][j] > h and ch[i][j] == 0: # h보다 높아야 안정영역이며, 방문하지 않은 곳을 발견
                cnt += 1
                dQ.append((i, j)) # 해당 좌표를 큐에 넣는다.
                while dQ: # 발견한 안전영역과 붙어 있는 곳을 찾는다.
                    x, y = dQ.popleft() # 해당 좌표부터 시작하여 상하좌우 안정영역을 찾는다.
                    for k in range(4):
                        nx = x + dx[k]
                        ny = y + dy[k]
                        if 0 <= nx < n and 0 <= ny < n and ch[nx][ny] == 0 and board[nx][ny] > h:
                            ch[nx][ny] = 1
                            dQ.append((nx, ny))
    result = max(result, cnt) # 해당 높이의 안전영역을 모두 찾은 후 높은 값을 result에 계속 업데이트 한다.
    
    if cnt == 0: # 안전영역이 0이라는 소리는 모든 영역이 물에 잠긴 것이므로, 그 이상의 높이는 당연히 잠기므로 더 볼 필요가 없다.
        break
        
print(result)