BOJ 2468

문제: 안전 영역 https://www.acmicpc.net/problem/2468

너버 우선 탐색(BFS, Breadth First Search)을 사용해서 푸는 문제

좋은 코드는 아니다. visited 초기화가 눈에 거슬린다.

# BOJ 2468 문제 풀어보기

import sys
from collections import deque

read = sys.stdin.readline

N = int(read())
P = [list(map(int, read().strip().split())) for _ in range(N)]
# print(N, P)

height_set = set()
for r in range(N):
    for c in range(N):
        height_set.add(P[r][c])
# print(height_set)

visited = [[0]*N for _ in range(N)]
# print(visited)


def bfs(start_r, start_c, w_height):
    if not P[start_r][start_c] > w_height:
        return 0
    queue = deque()
    queue.append([start_r, start_c])
    visited[start_r][start_c] = 1
    count = 1

    while queue:
        rr, cc = queue.popleft()
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nr, nc = rr + dr, cc + dc
            if not (-1 < nr < N and -1 < nc < N):
                # print("over boundary")
                continue
            if P[nr][nc] > w_height and visited[nr][nc] == 0:
                # print(nr, nc)
                queue.append([nr, nc])
                visited[nr][nc] = 1
                count += 1

    # print(start_r, start_c, w_height, count, visited)
    return count


def get_count(water_height):
    count = 0
    for rr in range(N):
        for cc in range(N):
            if visited[rr][cc] == 1:
                continue
            if bfs(rr, cc, water_height) > 0:
                count += 1
    return count


max_count = -1
# for height in height_set:
for height in range(max(height_set)):
    max_count = max(get_count(height), max_count)
    # print(visited)
    visited = [[0]*N for _ in range(N)]
    # print(max_count)

print(max_count)