[Python] boj no. 2423 : 전구를 켜라

Problem

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

Idea

우선 각 지점의 패턴 방향은 / 혹은 \로 두가지만 존재한다. 이때, 한 지점에서 인접한 다른 지점으로 이동하기 위한 경우의 수는 다음과 같다.

1. 현재 지점과 상하좌우로 인접한 지점으로 이동하는 경우,
   • 현재 지점과 이동 지점의 패턴 방향이 같으면 다음 이동 지점을 회전한 이후 이동할 수 있다.
   • 현재 지점과 이동 지점의 패턴 방향이 다르면 회전할 필요 없이 이동할 수 있다.
2. 현재 지점과 대각으로 인접한 지점으로 이동하는 경우 / 인 경우 1시와 7시, \인 경우 11시와 5로만 이동할 수 있다.
   • 현재 지점과 이동 지점의 패턴 방향이 같으면 회전할 필요 없이 이동할 수 있다.
   • 현재 지점과 이동 지점의 패턴 방향이 다르면 다음 이동 지점을 회전한 이후 이동할 수 있다.

경우의 수를 나눌 때 중요한 점은 현재 지점의 방향을 움직이는 경우의 수는 포함되면 안된다는 것이다. 현재 지점 또한 이전까지의 탐색 과정을 통해 최소 이동 횟수가 구해진 상태이기 때문이다.

결국 다음 이동지점으로 이동하기 위해 필요한 회전 수는 0 혹은 1이다. 따라서 0-1 bfs를 응용하여 회전 횟수가 필요하지 않은 경우 덱의 front에, 회전 횟수가 필요한 경우 덱의 rear에 삽입하며 너비 우선 탐색을 했다.

Code

import sys
from collections import deque

def bfs():
    dq = deque()
    if map[0][0] == 0:
        dist[0][0][0] = 0
    else:
        dist[1][0][0] = 1
        dist[0][0][0] = 1
    dq.append((0, 0, 0))

    while dq:
        py, px, pt = dq.popleft()
        rt = 1 if pt != 1 else 0

        for i in range(4):  # 상하좌우
            ny, nx = py+dy[i], px+dx[i]

            if 0 <= ny < N and 0 <= nx < M:
                nt = map[ny][nx]

                if pt == nt and dist[pt][py][px] + 1 < dist[rt][ny][nx]:    # 서로 같은 방향의 경우
                    dist[rt][ny][nx] = dist[pt][py][px] + 1
                    dq.append((ny, nx, rt))
                elif pt != nt and dist[pt][py][px] < dist[nt][ny][nx]:      # 서로 다른 방향의 경우
                    dist[nt][ny][nx] = dist[pt][py][px]
                    dq.appendleft((ny, nx, nt))

        if pt == 0:     # '\'
            for i in range(2):
                ny, nx = py+ddy[i], px+ddx[i]

                if 0 <= ny < N and 0 <= nx < M:
                    nt = map[ny][nx]

                    if pt == nt and dist[pt][py][px] < dist[nt][ny][nx]:    # 서로 같은 방향
                        dist[nt][ny][nx] = dist[pt][py][px]
                        dq.appendleft((ny, nx, pt))
                    elif rt == nt and dist[pt][py][px] + 1 < dist[pt][ny][nx]:  # 서로 다른 방향
                        dist[pt][ny][nx] = dist[pt][py][px] + 1
                        dq.append((ny, nx, pt))

        else:   # '/'
            for i in range(2, 4):
                ny, nx = py+ddy[i], px+ddx[i]

                if 0 <= ny < N and 0 <= nx < M:
                    nt = map[ny][nx]

                    if pt == nt and dist[pt][py][px] < dist[nt][ny][nx]:    # 서로 같은 방향
                        dist[nt][ny][nx] = dist[pt][py][px]
                        dq.appendleft((ny, nx, nt))
                    elif rt == nt and dist[pt][py][px] + 1 < dist[pt][ny][nx]:  # 서로 다른 방향
                        dist[pt][ny][nx] = dist[pt][py][px] + 1
                        dq.append((ny, nx, pt))

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

N, M = map(int, sys.stdin.readline().split())

map = [list(map(lambda x: 0 if x=='\\' else 1, sys.stdin.readline().rstrip())) for _ in range(N)]
dist = [[[sys.maxsize for _ in range(M)] for _ in range(N)] for _ in range(2)]

bfs()

if dist[0][N-1][M-1] == sys.maxsize:
    print("NO SOLUTION")
else:
    print(dist[0][N-1][M-1])

Comment

처음에 풀 때는 어느 지점까지 도달하는데 필요한 최소 회전 수를 저장하는 삼차원 리스트 dist를 사용했다. 하지만 결국은 bfs로 탐색할 것이기 때문에 deque의 파라메터에 현재 회전 수를 포함하여 탐색했더라면 리스트의 선언으로 인한 메모리 사용을 줄일 수 있었지 않았을까 생각한다.

test case:

7 7
\/\/\//
\/\////
\//\//\
\/\////
\//\//\
\/\////
\/\////

ans : 2