[백준] 2468번 안전 영역

💡문제접근

• BFS 탐색 알고리즘을 이용해서 문제를 해결할 수 있었다.
• 처음 제출한 코드는 2차원 배열에서 최솟값부터 최댓값까지 range로 범위를 지정해서 탐색한 코드였는데 해당 코드가 WA를 받아서 문제를 자세히 읽어봤는데 문제 하단부에 노트라는 부분에 힌트가 있었다.
• 아무 지역도 물에 잠기지 않을 수 있다. 비의 양을 나타내는 for문의 범위를 0부터 탐색해야한다.

💡코드(메모리 : 34192KB, 시간 : 1044ms)

from collections import deque
import sys
input = sys.stdin.readline

N = int(input().strip())
area = [list(map(int, input().strip().split())) for _ in range(N)]

def BFS(x, y, rain):
    cnt = 0
    queue = deque()
    queue.append((x, y))
    visited[x][y] = True
    while queue:
        x, y = queue.popleft()
        dx = [0, 1, 0, -1]
        dy = [-1, 0, 1, 0]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= N or ny < 0 or ny >= N:
                continue
            if 0 <= nx < N and 0 <= ny < N and area[nx][ny] > rain and not visited[nx][ny]:
                visited[nx][ny] = True
                queue.append((nx, ny))

result = 0
for h in range(101):
    cnt = 0
    visited = [[False] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if area[i][j] > h and not visited[i][j]:
                BFS(i, j, h)
                cnt += 1
    if result < cnt:
        result = cnt
print(result)

💡소요시간 : 10m