백준(BOJ) #2468 안전영역, 그리고 BFS 메모리초과

최종코드는 맨 아래에 있습니다!

내 코드

import sys
from collections import deque
di = [-1, 1, 0, 0]
dj = [0, 0, -1, 1]

N = int(sys.stdin.readline().rstrip()) # 행, 열의 개수를 나타내는 n
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

# arr에 있는 값중에 최소, 최대 값을 찾아서 brute-force를 진행한다.
min_num = min(min(arr))
max_num = max(max(arr))
numbers = [i for i in range(min_num, max_num+1)]

max_V = 1

def rain(number, list): # 강수량에 따라 잠겼는지를 체크할 함수
    for i in range(N):
        for j in range(N):
            if arr[i][j] <= number:
                list[i][j] = 1

def bfs(q):
    while q:
        si, sj = q.popleft()
        check[si][sj] = 1
        for d in range(4):
            ni, nj = si+di[d], sj+dj[d]
            if 0 <= ni < N and 0 <= nj < N and check[ni][nj] == 0:
                q.append((ni, nj))


def find(): # 안전지대의 개수를 셀 함수
    cnt = 0
    q = deque()
    for i in range(N):
        for j in range(N):
            if check[i][j] == 0:
                cnt += 1
                q.append((i, j))
                bfs(q)
    return cnt

for number in numbers:
    check = [[0]*N for _ in range(N)]
    rain(number, check)
    max_V = max(find(), max_V)

print(max_V)

복잡해보이지만 결국 브루투 포스 + BFS를 더한 것이라 충분히 이해되는 코드라고 생각한다.

답은 잘 출력되는데 5% 정도 진행되다가 ‘메모리초과’ 가 발생했다.

으잉? 싶어서 검색 + 공부한 결과 visit 체크하는 곳에서 과도한 메모리를 발생시키는 것을 알게 되었다.

그러니까 지금은 우선 append 하고 → pop 하면서 visit에 체크하는 방식인데,

이렇게 진행하면 중복으로 append 되는 것 때문에 메모리 초과가 발생한다.

즉, 먼저 visit 체크하고 → append 하는 방식이 메모리 초과를 발생시키지 않는다는 것이다.

그리고 0/1 int형으로 작성하는 것보다, True/False Boolean 형으로 작성하는 것이 메모리를 덜 잡아먹는다.

SWEA는 메모리, 시간초과에 대해서 관대해서 그냥 풀었는데

백준으로 넘어오니 확실히 신경쓸 것이 생긴다! 오늘의 배움 플러스

최종코드

import sys
from collections import deque
sys.setrecursionlimit(1000000)
di = [-1, 1, 0, 0]
dj = [0, 0, -1, 1]

N = int(sys.stdin.readline().rstrip()) # 행, 열의 개수를 나타내는 n
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

# arr에 있는 값중에 최소, 최대 값을 찾아서 brute-force를 진행한다.
min_num = min(min(arr))
max_num = max(max(arr))
numbers = [i for i in range(min_num, max_num+1)]

max_V = 1

def rain(number, list): # 강수량에 따라 잠겼는지를 체크할 함수 (잠기면1, 아니면0으로 처리)
    for i in range(N):
        for j in range(N):
            if arr[i][j] <= number:
                list[i][j] = 1

def bfs(q):
    while q:
        si, sj = q.popleft()
        for d in range(4):
            ni, nj = si+di[d], sj+dj[d]
            if 0 <= ni < N and 0 <= nj < N and check[ni][nj] == 0:
                q.append((ni, nj))
                check[ni][nj] = 1


def find(): # 안전지대의 개수를 셀 함수
    cnt = 0
    q = deque()
    for i in range(N):
        for j in range(N):
            if check[i][j] == 0:
                cnt += 1
                check[i][j] = 1
                q.append((i, j))
                bfs(q)
    return cnt

for number in numbers:
    check = [[0]*N for _ in range(N)]
    rain(number, check)
    max_V = max(find(), max_V)

print(max_V)

Uploaded by N2T