Jin의 일상

BFS에 조금 변형을 줘서 풀 수 있는 문제다.

일반적으로 BFS는 큐 자료구조를 통해 풀 수 있다.

큐는 선입 선출(FIFO)이므로, 기본 컨셉에 따르면 맨 뒤에 새로운 값을 넣어준 뒤 맨 앞에서 값을 빼내야 한다.

그런데 이 문제의 특정 조건에서는 큐의 맨 앞에 새로운 값을 넣어준다.

이 방법을 통해 우선적으로 탐색되어야 할 좌표에 가중치를 부여한 것이다.

어쨌든, 인풋되는 방식만 다를 뿐 알고리즘은 똑같이 작동한다.

나는 두 가지 방식으로 알고스팟 문제를 풀었는데, 앞에서 설명한 것이 A 방식이다.

B 방식은 다음 좌표의 값이 현재 좌표의 값보다 작다면 이동하는 방식을 취하고 있다.

전형적인 BFS에 조건을 하나 추가한 것이다.  하지만 채점의 63%정도 구간에서 메모리 초과로 테스트를 통과하지 못했다. 그래도 테스트 케이스는 모두 통과할 것으로 생각된다.

메모리 초과한 원인을 분석하기 위해 BFS 진행 간 A와 B 방식의 Queue 값을 출력했다.

A 코드는 우선적으로 탐색해야 할 좌표에 가중치를 부여했으므로, 불필요한 탐색이 깊게 진행되지 않았다. 

반면에 B 코드는 이전에 4번의 벽을 부수고 이동했는데, 이번에 3번 벽을 이동한 경로가 발견됐다면 3으로 갱신하고 다음 번에 1번만 벽을 부수어도 된다면 다시 갱신하고,. ..... 이렇게 반복해야 한다. 따라서 불필요한 탐색이 깊게 진행된다.

그래서 Queue에 저장될 좌표도 많아질 수 밖에 없던 것이다.

A 코드

# A 코드: 좌표의 상태에 따라 가중치를 부여함 

import sys
from collections import deque

INPUT = sys.stdin.readline
DIRECTION = ((0, 1), (0, -1), (1, 0), (-1, 0))


def solution():
    m, n = map(int, INPUT().split())
    board = [list(map(int, INPUT().rstrip())) for _ in range(n)]
    visited = [[-1] * m for _ in range(n)]

    visited[0][0] = 0
    q = deque([[0, 0]])
    while q:
        x, y = q.popleft()

        for i in range(4):
            next_x = x + DIRECTION[i][0]
            next_y = y + DIRECTION[i][1]

            if (0 > next_x or next_x >= m) or (0 > next_y or next_y >= n):
                continue

            if visited[next_y][next_x] != -1:
                continue

            if board[next_y][next_x] == 0:
                visited[next_y][next_x] = visited[y][x]
                q.appendleft([next_x, next_y])
            else:
                visited[next_y][next_x] = visited[y][x] + 1
                q.append([next_x, next_y])
    return visited[n-1][m-1]
print(solution())

B 코드 

# B 코드: 좌표별 상태에 따라 가중치를 부여하지 않음. (메모리 초과)

import sys
from collections import deque

INPUT = sys.stdin.readline
MAX = 9999999
DIRECTION = ((0, 1), (0, -1), (1, 0), (-1, 0))


def solution():
    m, n = map(int, INPUT().split())
    board = [list(map(int, INPUT().rstrip())) for _ in range(n)]
    visited = [[MAX] * m for _ in range(n)]

    visited[0][0] = 0
    q = deque([[0, 0]])
    while q:
        x, y = q.popleft()

        for i in range(4):
            next_x = x + DIRECTION[i][0]
            next_y = y + DIRECTION[i][1]

            if (0 > next_x or next_x >= m) or (0 > next_y or next_y >= n):
                continue

            if visited[next_y][next_x] <= visited[y][x]:
                continue

            if board[next_y][next_x] == 0:
                visited[next_y][next_x] = visited[y][x]
                q.appendleft([next_x, next_y])
            else:
                visited[next_y][next_x] = visited[y][x] + 1
                q.append([next_x, next_y])
    return visited[n-1][m-1]
print(solution())