[Python] 백준 2468 : 안전 영역

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

2468번: 안전 영역

Logic

문제 자체는 일반적인 bfs문제 스타일이다. 메모리 초과나 런타임 에러를 처리해주는 과정이 문제 자체를 풀어나가는 과정보다 더욱 까다로웠다. 최저 지대와 최대 지대를 구한 후, 비가 최저 지대에서 최대 지대까지 올 경우를 전부 구해주는 것을 목적으로 했다.

첫 시도

from collections import deque
dir = [(0,-1),(0,1),(-1,0),(1,0)]

def bfs(r,c,rain):
    q = deque()
    q.append((r,c))
    visited[r][c] = True
    while q:
        r,c = q.popleft()
        for k in range(4):
            nr = r + dir[k][0]
            nc = c + dir[k][1]
            if 0<=nr<N and 0<=nc<N and not visited[nr][nc] and arr[nr][nc]>rain:
                visited[nr][nc] = True
                q.append((nr,nc))
    return

N = int(input())
arr = []
maxV = 0
minV = 999
cnt = 0
ans = []
for _ in range(N):
    lst = list(map(int, input().split()))
    if maxV < max(lst):
        maxV = max(lst)
    if minV>min(lst):
        minV = min(lst)
    arr.append(lst)


while minV != maxV:
    cnt = 0
    visited = [[False] * N for _ in range(N)]

    for r in range(N):
        for c in range(N):
            if arr[r][c] > minV and not visited[r][c]: #잠기지 않을 경우
                bfs(r,c,minV)
                cnt += 1
    minV += 1
    ans.append(cnt)
print(max(ans))

대충 이런 식으로 문제를 접근하려고 했으나... Pycharm에서는 답이 잘 나왔는데 백준에서는 런타임 에러와 메모리 초과가 나왔다.

 

 

ANS

import sys
input = sys.stdin.readline
from collections import deque
import copy
dir = [(0, -1), (0, 1), (-1, 0), (1, 0)]


def bfs(r, c, rain):
    q = deque()
    q.append((r, c))
    visited[r][c] = True
    while q:
        r, c = q.popleft()
        for k in range(4):
            nr = r + dir[k][0]
            nc = c + dir[k][1]
            if 0 <= nr < N and 0 <= nc < N and not visited[nr][nc] and arr[nr][nc] > rain:
                visited[nr][nc] = True
                q.append((nr, nc))
    return

N = int(input())
maxV = 0
minV = 0
ans = []

arr = [list(map(int, input().split())) for _ in range(N)]
for i in arr:
    if maxV < max(i):
        maxV = max(i)
visited_base = [[False] * N for _ in range(N)]

while minV != maxV:
    cnt = 0
    visited = copy.deepcopy(visited_base)
    for r in range(N):
        for c in range(N):
            if arr[r][c] > minV and not visited[r][c]:
                bfs(r, c, minV)
                cnt += 1
    minV += 1
    ans.append(cnt)
print(max(ans))

첫번째 도전에서 직면한 문제들을 해결하기 위해 잘못(혹은 과도하게)설정된 변수나 리스트는 없는지를 자세하게 살펴보았고... minV와 maxV를 모두 구하는 과정이 굳이? 싶어서 maxV만 구하고 minV는 0에서부터 처리해주고자 했다. deepcopy를 사용하여 비의 높이가 높아질 때마다 visited를 새로 만들어주었다!