[백준 알고리즘] 2468번 안전 영역, 파이썬(python)

2468, 안전 영역

📁 문제 출처

2468번: 안전 영역

 

💡 생각

• 문제 이해를 못해서 다른 사람들의 풀이를 여러 번 보고 이해할 수 있었다.
• "안전한 영역의 최대 개수", "아무 지역도 물에 잠기지 않을 수도 있다." 이 두 문장이 문제의 핵심이다.
• 일단 비가 얼마나 오는지 모른다. -> 비가 오는 양은 0부터 배열에 있는 최고 높이까지 온다.
• 최고 높이까지 오면 모두 잠기기 때문에 최고 높이-1 까지만 계산한다.
• 예를 들면 최고 높이가 9라면 0부터 8까지 다 돌고 안전한 영역의 최대 개수를 구하면 된다.

 

🛠 나의 코드

from 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
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)

 

✔️ 배운 점 및 주의할 점

• 이 문제를 이해하고 풀고 또는 다른 사람의 코드를 이해하는데 많은 시간이 걸렸다.
• 이전에 풀었던 bfs는 이미 그래프에 모두 체크가 되어 있는 상태에서 조건문을 통해(ex. if graph[i][j] == 1:) 만들어 놓은 bfs 함수를 실행시키는 반면 이 문제에서는 graph[j][k] > i and visited[j][k] == 0을 통해서 조건의 반대? 부분을 체크해 나가는 문제이다. (머리로는 이해했는데 글로 표현을 잘 못하겠습니다..)
• 그리고 맨 처음에는 그래프를 어떻게 복사하지라고 생각했는데 visited 그래프를 매번 생성해주고 for문을 돌리면 된다.