티스토리 뷰

[Silver I] 돌다리 - 12761

문제 링크

성능 요약

메모리: 33496 KB, 시간: 292 ms

분류

너비 우선 탐색(bfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal)

문제 설명

동규와 주미는 일직선 상의 돌 다리 위에있다. 돌의 번호는 0 부터 100,000 까지 존재하고 동규는 N번 돌 위에, 주미는 M번 돌 위에 위치하고 있다. 동규는 주미가 너무 보고싶기 때문에 최대한 빨리 주미에게 가기 위해 A,B 만큼의 힘을 가진 스카이 콩콩을 가져왔다. 동규가 정한 다리를 건너는 규칙은 턴 방식인데, 한 턴에 이동할 수 있는 거리는 이러하다. 현 위치에서 +1칸, -1칸을 이동할 수 있고, 스카이 콩콩을 이용해 현 위치에서 AB만큼 좌우로 점프할 수 있으며, 순간적으로 힘을 모아 현 위치의 A배나 B배의 위치로 이동을 할 수 있다. 예를 들어 지금 동규가 7번 돌 위에 있고 스카이 콩콩의 힘이 8이면 그냥 점프를 해서 15번 돌에 갈 수도 있고, 순간적으로 힘을 모아 56번 돌에 갈 수도 있다는 것이다. 주어진 8가지의 방법 중 적절한 방법을 골라서 최대한 빨리 동규가 주미를 만날 수 있게 도와주자. 단, 이동 과정에서 100,000보다 크거나 0보다 작은 번호의 돌은 존재하지 않으므로 갈 수 없고, 같은 방법을 계속 사용해도 되며 항상 도달할 수 있는 케이스만 주어진다.

입력

입력의 첫 줄에 스카이 콩콩의 힘 AB, 그리고 동규의 현재위치 N, 주미의 현재 위치 M이 주어진다. (단, 2A,B30 이고 0N,M100,000)

출력

동규가 주미에게 도달하기 위한 최소한의 이동 횟수를 출력하라.

문제 링크

성능 요약

메모리: 33496 KB, 시간: 292 ms

분류

너비 우선 탐색(bfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal)

문제 설명

동규와 주미는 일직선 상의 돌 다리 위에있다. 돌의 번호는 0 부터 100,000 까지 존재하고 동규는 N\(N\)번 돌 위에, 주미는 M\(M\)번 돌 위에 위치하고 있다. 동규는 주미가 너무 보고싶기 때문에 최대한 빨리 주미에게 가기 위해 A,B\(A, B\) 만큼의 힘을 가진 스카이 콩콩을 가져왔다. 동규가 정한 다리를 건너는 규칙은 턴 방식인데, 한 턴에 이동할 수 있는 거리는 이러하다. 현 위치에서 +1칸, -1칸을 이동할 수 있고, 스카이 콩콩을 이용해 현 위치에서 A\(A\)나 B\(B\)만큼 좌우로 점프할 수 있으며, 순간적으로 힘을 모아 현 위치의 A\(A\)배나 B\(B\)배의 위치로 이동을 할 수 있다. 예를 들어 지금 동규가 7번 돌 위에 있고 스카이 콩콩의 힘이 8이면 그냥 점프를 해서 15번 돌에 갈 수도 있고, 순간적으로 힘을 모아 56번 돌에 갈 수도 있다는 것이다. 주어진 8가지의 방법 중 적절한 방법을 골라서 최대한 빨리 동규가 주미를 만날 수 있게 도와주자. 단, 이동 과정에서 100,000보다 크거나 0보다 작은 번호의 돌은 존재하지 않으므로 갈 수 없고, 같은 방법을 계속 사용해도 되며 항상 도달할 수 있는 케이스만 주어진다.

입력

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

출력

동규가 주미에게 도달하기 위한 최소한의 이동 횟수를 출력하라.

from collections import deque


def bfs(graph, n):
      visited = [0] * 100001
      q = deque()
      q.append(n)
      visited[n] = 1

      while q:
            x = q.popleft()

            for i in range(8):
                  if i < 6:
                        nx = x + dx[i]
                  else:
                        nx = x * dx[i]

                  if 0 <= nx <= 100000 and visited[nx] == 0:
                        graph[nx] = graph[x] + 1
                        visited[nx] = 1
                        q.append(nx)



# 스카이콩콩 a | b 의 힘 , 동규와 주미의 현재 위치 n m
a, b, n, m = map(int, input().split())

dx = [1, -1, a, b, -a, -b, a, b]

graph = [0] * 100001
bfs(graph, n)
print(graph[m])

'코딩테스트 > 백준' 카테고리의 다른 글

파이썬 | 16918 봄버맨 _ S1  (0) 2022.07.04
파이썬 | 16948 . 데스 나이트 _S1  (0) 2022.06.25
파이썬 | 2583 영역 구하기 S1  (0) 2022.06.19
파이썬 | 2468 안전영역 S1  (0) 2022.06.19
파이썬 | 1926_그림_S1  (0) 2022.06.16
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/01   »
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함