BOJ_12761 [ 돌다리 ] [ 파이썬 ]

문제

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

12761번: 돌다리

문제 해결 방법

bfs로 문제 해결 방법을 접근했습니다.

총 이동 가능한 경우 8가지를 현재 위치에서 다음 위치를 계산해서

범위를 벗어나지 않았고 처음 방문했다면 큐에 넣으면 된다.

 

소스 코드 보기

https://github.com/jokerKwu/BOJ_Algorithm/blob/master/python/BOJ_12761.py

jokerKwu/BOJ_Algorithm

from collections import deque
import sys
input = sys.stdin.readline
A, B, N, M = map(int,input().split())
m_x = [1, -1, A, B, -A, -B, A, B]
visit = [0 for _ in range(100001)]
cnt = [0 for _ in range(100001)]
q = deque()
visit[N] = 1
q.append(N)
def bfs():
    while q:
        x = q.popleft()
        for i in range(8):
            if i < 6:
                nx = x + m_x[i]
                if 0<=nx<=100000 and visit[nx] == 0:
                    visit[nx] = 1
                    q.append(nx)
                    cnt[nx] = cnt[x] + 1
            else:
                nx = x * m_x[i]
                if 0<=nx<=100000 and visit[nx] == 0:
                    visit[nx] = 1
                    q.append(nx)
                    cnt[nx] = cnt[x] + 1
bfs()
print(cnt[M])