[BOJ] 2468. 안전 영역(Python) / BFS

www.acmicpc.net/problem/2468

2468번: 안전 영역

어렵지 않은 BFS 문제였다. 실제로 난이도 실버1.

• 기본적인 BFS 틀에 조건만 이동할 위치를 현재 비의 양과 비교해 더 높을 때마다 BFS를 확장시켰다.
• 이 때, 비의 양이 달라질 때마다 경우가 달라지므로 나름의 아이디어를 내서
  • visited를 재활용하기 위해 새로 방문 표시를 할 때는 현재 비의 양으로 표현해 비의 양이 다른 경우와 구분했다.
• 비의 양을 결정한 후 결과(안전영역의 갯수, temp)가 나올 때마다 MAX 값을 갱신해준다.

 

파이썬 코드는 다음과 같다.

---

import sys
input = sys.stdin.readline

from collections import deque

dr = (-1, 1, 0, 0)
dc = (0, 0, -1, 1)

def bfs(sr, sc, rain):
    Q = deque([(sr, sc)])
    visited[sr][sc] = rain
    while Q:
        r, c = Q.popleft()
        for d in range(4):
            nr = r + dr[d]
            nc = c + dc[d]
            if not (0 <= nr < N and 0 <= nc < N):
                continue
            if A[nr][nc] <= rain:
                continue
            if visited[nr][nc] == rain:
                continue
            visited[nr][nc] = rain
            Q.append((nr, nc))
    return 1

# main
N = int(input())
top = 0
A = []
for i in range(N):
    A.append(list(map(int, input().split())))
    for j in range(N):
        top = max(top, A[i][j])

MAX = float('-inf')
visited = [[-1] * N for _ in range(N)]
for rain in range(top+1):
    temp = 0
    for sr in range(N):
        for sc in range(N):
            if A[sr][sc] > rain and visited[sr][sc] != rain:
                temp += bfs(sr, sc, rain)
    MAX = max(MAX, temp)
print(MAX)

---

• 시간 : 280ms / 메모리 126796kb
• 고찰 : 요새 BFS 위주로 풀고 있는 것 같다, 내가 비교적 약한 DFS, DP 문제 풀이에 좀더 집중해야겠다. 곧 있으면 코테를 와장창 볼 텐데 원하는 기업 코테에 통과할 수 있도록 꾸준히 코딩하고 사고하자. 파이팅!