[백준] 2468번: 안전 영역 (python)

https://www.acmicpc.net/problem/2468

---

BFS를 사용하여 문제를 풀이하였다.

문제 풀이의 포인트는 지도를 저장하며 최대 높이를 구하여 최대 높이 전까지만 물이 차는 경우를 모두 탐색한다.

또한, 잠기지 않은 땅인 경우에 해당 영역 기준으로 BFS를 통하여 주변 영역들을 순회하며 잠기지 않은 영역을 구분하고 카운트한다.

마지막으로 카운트 된 갯수 중 가장 큰 값을 출력하면 된다.

---

from collections import deque

def bfs(x, y, num):
    q = deque([(x, y)])
    visited[x][y] = True
    while q:
        n_x, n_y = q.popleft()
        
        # 상하좌우 방향 탐색
        for i in range(4):
            nx, ny = n_x + dx[i], n_y + dy[i]
            # 지도 밖으로 나간 경우 확인
            if 0 <= nx < n and 0 <= ny < n:
            	# 잠기지 않고 아직 방문하지 않은 경우 큐에 추가
                if maps[nx][ny] > num and not visited[nx][ny]:
                    q.append((nx, ny))
                    visited[nx][ny] = True


n = int(input())
max_num = 0
maps = []

# 지도를 저장하며 가장 높은 지역의 높이를 저장합니다
for _ in range(n):
    m = list(map(int, input().split()))
    maps.append(m)
    for i in m:
        if i > max_num:
            max_num = i

# 탐색 영역
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

ans = []

# 0부터 가장 높은 지역 높이의 전까지 물이 차는 경우 잠기지 않는 영역 모두 탐색
for i in range(max_num):
	# 방문 영역 처리를 위한 테이블 생성
    visited = [[False] * n for _ in range(n)]
    # 잠기지 않는 영역 카운트
    cnt = 0
    for j in range(n):
        for k in range(n):
        	# 잠기지 않고 방문하지 않았다면 BFS로 연결된 영역 탐색
            if maps[j][k] > i and not visited[j][k]:
                bfs(j, k, i)
                cnt += 1
    ans.append(cnt)

print(max(ans))