[baekjoon] 백준 12761번(파이썬): 돌다리

문제

12761번: 돌다리

- 동규와 주미는 일직선 상의 돌 다리 위에있다.

- 돌의 번호는 0 부터 100,000 까지 존재하고 동규는 N번 돌 위에, 주미는 M번 돌 위에 위치하고 있다.

- 동규는 주미가 너무 보고싶기 때문에 최대한 빨리 주미에게 가기 위해 A,B 만큼의 힘을 가진 스카이 콩콩을 가져왔다.

- 동규가 정한 다리를 건너는 규칙은 턴 방식인데, 한 턴에 이동할 수 있는 거리는 이러하다.

- 현 위치에서 +1칸, -1칸을 이동할 수 있고, 스카이 콩콩을 이용해 현 위치에서 A나 B만큼 좌우로 점프할 수 있으며, 순간적으로 힘을 모아 현 위치의 A배나 B배의 위치로 이동을 할 수 있다. 예를 들어 지금 동규가 7번 돌 위에 있고 스카이 콩콩의 힘이 8이면 그냥 점프를 해서 15번 돌에 갈 수도 있고, 순간적으로 힘을 모아 56번 돌에 갈 수도 있다는 것이다. 

- 주어진 8가지의 방법 중 적절한 방법을 골라서 최대한 빨리 동규가 주미를 만날 수 있게 도와주자.

- 단, 이동 과정에서 100,000보다 크거나 0보다 작은 번호의 돌은 존재하지 않으므로 갈 수 없고, 같은 방법을 계속 사용해도 되며 항상 도달할 수 있는 케이스만 주어진다.

- 스카이 콩콩의 힘 A와 B, 그리고 동규의 현재위치 N, 주미의 현재 위치 M이 주어진다. (단, 2≤A,B≤30 이고  0≤N,M≤100,000)

- 동규가 주미에게 도달하기 위한 최소한의 이동 횟수를 구하는 문제이다.

알고리즘

- bfs 탐색을 통해 문제를 수행한다.

- +1, -1, +a, -a, +b, -b, *a, *b 총 8가지 방법으로 이동하는 것을 bfs로 탐색

- 매 순간 이동할 칸에 현재 턴 + 1을 해준다.(이동할 칸까지 가야 할 턴)

코드

import sys
from collections import deque


def bfs(x):
    # +1, -1, +a, -a, +b, -b, *a, *b칸 이동
    dy = [1, -1, a, -a, b, -b, a, b]
    queue = deque([x])
    visited[x] = True
    while queue:

        # 현재 위치 확인
        target = queue.popleft()

        # 현재 위치에서 총 8가지 경우의 수를 bfs 탐색으로 수행
        for i in range(8):
            # 6가지 경우는 + 연산
            if i < 6:

                y = target + dy[i]

                # 현재 위치와 이동하는 수를 더한 값이 돌다리 위에 있고 탐색하지 않았다면
                # 큐에 추가하고 그때의 턴을 +1 해준다.
                if 0 <= y <= 100000 and visited[y] == False:
                    queue.append(y)
                    visited[y] = True
                    graph[y] = graph[target] + 1

            # 나머지 2개의 경우는 배수이기 때문에 곱하기로 연산
            else:

                y = target * dy[i]

                # 현재 위치와 이동하는 수를 곱한 값이 돌다리 위에 있고 탐색하지 않았다면
                # 큐에 추가하고 그때의 턴을 +1 해준다.
                if 0 <= y <= 100000 and visited[y] == False:
                    queue.append(y)
                    visited[y] = True
                    graph[y] = graph[target] + 1


a, b, n, m = map(int, sys.stdin.readline().split())
graph = [0 for _ in range(100001)]
visited = [False for _ in range(100001)]

# dfs 탐색
bfs(n)

# 결과값 출력
print(graph[m])

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법