[python] 백준 2468번 안전 영역

백준 2468번 안전 영역

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

문제

풀이

이런 그룹화? 묶음 세기 는 무조건 dfs 로 푸는데, dfs 로 풀고 최적화 를 해도 계속 런타임에러가 떠서 bfs 로 바꿔 풀었다.

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())
graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))

maxnum = max(max(row) for row in graph)

# BFS 함수 정의
def bfs(x, y, height, visited):
    queue = deque([(x, y)])
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    visited[x][y] = True

    while queue:
        x, y = queue.popleft()
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and graph[nx][ny] > height:
                visited[nx][ny] = True
                queue.append((nx, ny))

# 모든 가능한 높이에 대해 안전 영역 계산
answer = []
for height in range(0, maxnum + 1):  # 수정: minnum이 아니라 0에서 시작
    visited = [[False] * n for _ in range(n)]
    count = 0
    for i in range(n):
        for j in range(n):
            if graph[i][j] > height and not visited[i][j]:
                bfs(i, j, height, visited)
                count += 1
    answer.append(count)

print(max(answer))

📌 주의

• return 할 게 없으면 굳이 하지말자.
• 여기서 가장 중요한 포인트는 if graph[i][j] > height and not visited[i] 이거다. 항상 그래프를 바꾸는 나이기에, 이번에도 그래프를 0,1 로 바꾸어보았는데, 그러다보니 height 가 반복되면 될수록 기이한 숫자를 만나볼 수 있었다. 따라서 visited 를 사용해서, 안 방문한 노드만 쏙쏙 갈 수 있게...
• 또 하나 희한한 것. minnum에서 시작하는 거로 하니까 틀렸습니다 가 뜨더라?? 0에서 시작하는 거로 바꾸니 정답이 나오는 건 왜일까? (답을 찾지 못했음)