[백준 16137] 견우와 직녀 - Python

문제 보기

[사용한 알고리즘]

BFS(너비 우선 탐색)

 

[문제 접근]

일반적인 BFS 최단 거리 문제와 달리 가장 먼저 발견한 경로가 최단 경로가 아닐 수 있습니다. 따라서 이동할 수 있는 모든 경로를 BFS 방식으로 확인하였습니다.

 

[알고리즘]

1. 견우의 시작점 (0, 0)에서 출발합니다.

2. 상, 하, 좌, 우로 이동할 수 있는 위치가 있는지 확인합니다.

 - 1은 바로 이동할 수 있습니다.

 - 오작교를 연속해서 건널 수 없습니다.

 - 절벽이 교차하는 구간은 오작교를 설치할 수 없습니다.

 - 오작교는 시간 주기가 일치할 때((현재 시간 + 1) % 시간 주기 = 0) 이동할 수 있습니다.

3. 직녀를 만날 때마다 최단 경로 변수에 최단 값을 저장합니다.

 

[코드]

from collections import deque
import sys

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
INF = 1e9
answer = INF


def bfs():
    global answer
    q = deque()
    q.append((0, 0, 0, False, False))
    d = dict()
    d[(0, 0, False)] = 0

    while q:
        x, y, cnt, flag, cross = q.popleft()
        if cnt > answer:
            continue
        if x == n - 1 and y == n - 1:
            answer = min(answer, cnt)
            continue
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if maps[nx][ny] != 0:
                    if maps[nx][ny] == 1:
                        if cnt + 1 < d.get((nx, ny, flag), INF):
                            q.append((nx, ny, cnt + 1, flag, False))
                            d[(nx, ny, flag)] = cnt + 1
                    elif not cross:
                        if (cnt + 1) % maps[nx][ny] == 0:
                            t = cnt + 1
                        else:
                            t = cnt + (maps[nx][ny] - cnt % maps[nx][ny])
                        if t < d.get((nx, ny, flag), INF):
                            q.append((nx, ny, t, flag, True))
                            d[(nx, ny, flag)] = t
                else:
                    if not flag and not cross:
                        # (상, 우) 확인
                        temp = True
                        if nx - 1 >= 0 and ny + 1 < n:
                            if maps[nx - 1][ny] == 0 and maps[nx][ny + 1] == 0:
                                temp = False
                        # (상, 좌) 확인
                        if nx - 1 >= 0 and ny - 1 >= 0:
                            if maps[nx - 1][ny] == 0 and maps[nx][ny - 1] == 0:
                                temp = False
                        # (하, 우) 확인
                        if nx + 1 < n and ny + 1 < n:
                            if maps[nx + 1][ny] == 0 and maps[nx][ny + 1] == 0:
                                temp = False
                        # (하, 좌) 확인
                        if nx + 1 < n and ny - 1 >= 0:
                            if maps[nx + 1][ny] == 0 and maps[nx][ny - 1] == 0:
                                temp = False
                        if temp:
                            if (cnt + 1) % m == 0:
                                t = cnt + 1
                            else:
                                t = cnt + (m - cnt % m)
                            if t < d.get((nx, ny, True), INF):
                                q.append((nx, ny, t, True, True))
                                d[(nx, ny, True)] = t


if __name__ == "__main__":
    n, m = map(int, sys.stdin.readline().split())
    maps = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

    bfs()
    print(answer)