[python]백준 2468 안전영역

일단 상하좌우를 탐색해야하는 좌표라는 점에서 미로 예제가 생각났다
다만 미로 예제와는 달리 길이 막혀 갈 수 있는 길이 하나인게 아니라 사방이 둘러싸여 있는 영역이 몇개인지 세는것이였다.

구체적인 로직을 짜기 전에 일단 큰 틀 먼저 잡았다.
먼저 생각한 순서는
1. 일단 주어진 높이중 최대높이를 알아내 0부터 최대높이-1까지 알아본다.
(이 과정에서 1부터 최대높이-1까지로 생각해 계속해서 오류가 났다 높이가 1부터 시작하므로 0부터 봐줘야 한다) - > for문 하나

2. 각 좌표마다 확인을 해야한다 -> 이중 for문 필요

3. 한번 조건을 만족하는 좌표를 찾으면 막혀있지 않을 때까지 탐색해야한다 -> 조건 만족시 작동할 함수를 만든다.

rom collections import deque

n = int(input())
graph = []
maxNum = 0

for i in range(n):
    graph.append(list(map(int, input().split())))
    for j in range(n):
        if graph[i][j] > maxNum:
            maxNum = graph[i][j] 

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


def bfs(a,b,value,visited):
    q = deque()
    q.append((a,b))
    visited[a][b] = 1

    

    while(q):
        x,y = q.popleft()

        #안전영역일 때
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<n and 0<=ny<n:
                if graph[nx][ny]>value and visited[nx][ny] == 0:
                    visited[nx][ny] = 1
                    q.append((nx,ny))


result = 0

#강수량 1부터 최대높이까지 검사
for i in range(maxNum):
    visited = [[0] * n for i in range(n)]
    cnt = 0

    #각 강수량별 안전영역 개수 세기
    for j in range(n):
        for k in range(n):
            #안전영역에 속한지점이라면 함수 시작
            if  graph[j][k]>i and visited[j][k] == 0:
                bfs(j,k,i,visited)
                cnt+=1

    if result< cnt:
        result = cnt
    
print(result)

이런식으로 코드를 작성해주었다.
미로 문제에서 한번 더 꼬아서 생각해볼만한 문제였다.