[Algorithm] 백준 16933의 메모리 초과

기존 코드

#16933
import sys
from collections import deque

n, m, break_cnt = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]
visited = [[[False] * (break_cnt + 1) for _ in range(m)] for _ in range(n)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def bfs():
    queue = deque()
    queue.append((0, 0, 0, 1, 1))  # 시작 위치, 벽을 부순 횟수, 이동 거리 추가,밤낮여부(낮:1,밤:0)
    visited[0][0][0] = 1
    
    while queue:
        x, y, cur_break_cnt, distance, is_day = queue.popleft()

        # 도착 지점에 도달했을 경우
        if x == (n - 1) and y == (m - 1):
            return distance

        # 인접한 네 방향 탐색
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y

            # 범위 내에 있을 경우
            if 0 <= nx < n and 0 <= ny < m:
                # 벽이 있고, 벽을 부술 수 있으며, 방문하지 않은 경우
                if graph[nx][ny] == 1 and cur_break_cnt < break_cnt and not visited[nx][ny][cur_break_cnt + 1]:
                    if is_day:  # 낮인 경우
                        queue.append((nx, ny, cur_break_cnt + 1, distance + 1, 0))
                        visited[nx][ny][cur_break_cnt + 1] = True
                    else:
                        queue.append((x, y, cur_break_cnt, distance + 1, 1))

                # 벽이 없고 방문하지 않은 경우
                elif graph[nx][ny] == 0 and not visited[nx][ny][cur_break_cnt]:
                    visited[nx][ny][cur_break_cnt] = True
                    if is_day:
                        queue.append((nx, ny, cur_break_cnt, distance + 1, 0))
                    else:
                        queue.append((nx, ny, cur_break_cnt, distance + 1, 1))
    return -1


print(bfs())

 

수정 코드

#16933
import sys
from collections import deque

n, m, break_cnt = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]
visited = [[[0] * m for _ in range(n)] for _ in range(break_cnt + 1)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def bfs():
    queue = deque()
    queue.append((0, 0, 0, 1, 1))  # 시작 위치, 벽을 부순 횟수, 이동 거리 추가,밤낮여부(낮:1,밤:0)
    visited[0][0][0] = 1
    
    while queue:
        x, y, cur_break_cnt, distance, is_day = queue.popleft()

        # 도착 지점에 도달했을 경우
        if x == (n - 1) and y == (m - 1):
            return distance

        # 인접한 네 방향 탐색
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y

            # 범위 내에 있을 경우
            if 0 <= nx < n and 0 <= ny < m:
                # 벽이 있고, 벽을 부술 수 있으며, 방문하지 않은 경우
                if graph[nx][ny] == 1 and cur_break_cnt < break_cnt and not visited[cur_break_cnt + 1][nx][ny]:
                    if is_day:  # 낮인 경우
                        queue.append((nx, ny, cur_break_cnt + 1, distance + 1, 0))
                        visited[cur_break_cnt + 1][nx][ny] = 1
                    else:
                        queue.append((x, y, cur_break_cnt, distance + 1, 1))

                # 벽이 없고 방문하지 않은 경우
                elif graph[nx][ny] == 0 and not visited[cur_break_cnt][nx][ny]:
                    visited[cur_break_cnt][nx][ny] = 1
                    if is_day:
                        queue.append((nx, ny, cur_break_cnt, distance + 1, 0))
                    else:
                        queue.append((nx, ny, cur_break_cnt, distance + 1, 1))
    return -1


print(bfs())

 

 

차이점

: 메모리 접근 패턴이 다름

# 기존코드
visited = [[[False] * (break_cnt + 1) for _ in range(m)] for _ in range(n)]
 if graph[nx][ny] == 1 and cur_break_cnt < break_cnt and not visited[nx][ny][cur_break_cnt + 1]:
    if is_day:  # 낮인 경우
       queue.append((nx, ny, cur_break_cnt + 1, distance + 1, 0))
       visited[nx][ny][cur_break_cnt + 1] = True
       
# 바뀐코드

visited = [[[0] * m for _ in range(n)] for _ in range(break_cnt + 1)]
 if graph[nx][ny] == 1 and cur_break_cnt < break_cnt and not visited[cur_break_cnt + 1][nx][ny]:
    if is_day:  # 낮인 경우
       queue.append((nx, ny, cur_break_cnt + 1, distance + 1, 0))
       visited[cur_break_cnt + 1][nx][ny] = 1

 

 

기존코드 메모리 참조 방식 (불연속적 접근):   visited[0][0][0]에서 visited[0][0][1]로 점프해야함 -> 캐시 활용이 덜 효율적임

visited[0][0][0], visited[0][0][1], visited[0][1][0], visited[0][1][1], visited[0][2][0], visited[0][2][1], visited[1][0][0], visited[1][0][1], visited[1][1][0], visited[1][1][1], visited[1][2][0], visited[1][2][1], visited[2][0][0], visited[2][0][1], visited[2][1][0], visited[2][1][1], visited[2][2][0], visited[2][2][1]

 

바뀐코드 메모리 참조 방식(연속적 접근): cur_break_cnt값에 대해 (x,y)를 순회하며 메모리에 연속 접근함 -> 캐시 효율성을 높일 수 있음

# 벽을 부수지 않고 방문한 경우(0회 부숨): 
visited[0][0][0], visited[0][0][1], visited[0][0][2], visited[0][1][0], visited[0][1][1], visited[0][1][2], visited[0][2][0], visited[0][2][1], visited[0][2][2]
# 벽을 부수고 방문한 경우(1회 부숨): 
visited[1][0][0], visited[1][0][1], visited[1][0][2], visited[1][1][0], visited[1][1][1], visited[1][1][2], visited[1][2][0], visited[1][2][1], visited[1][2][2]

 

연속된 접근 vs. 불연속적인 접근

연속된 접근: 순차적으로 데이터를 읽을 경우 메모리의 연속된 주소를 차례대로 접근함

-> CPU캐시가 이러한 접근 패턴을 예측하고, 미리 다음에 필요할 데이터를 미리 캐시에 로드함

 

불연속적인 접근: 빈번하게 점프하며 데이터에 접근하는 경우 

-> CPU캐시가 예측을 할 수 없어 미리 데이터를 로드하기 어려움. 캐시미스 발생(CPU가 메인메모리에 직접 접근해, 메모리 대기 시간이 증가시킴)