링크 : https://www.acmicpc.net/problem/1697
1697번: 숨바꼭질
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
- 문제
- 소요시간: 18분 35초


- 설계하기(접근방법)
1. 입력받기
시작 지점과 목표 지점을 입력받는다
2. 구현하기
bfs 문제인데 배열을 만든다
nx = [-1, +1, i ==2 일 때 x *= 2]
visited 배열을 100001개를 선언해주고
nx의 범위 역시 100000을 벗어나지 않도록 해준다
각각의 케이스를 q에 apppend 하고
nx가 target 과 같다면
break를 해준다
해주지 않는다면 무한루프를 돈다
3. 출력하기
- 코드(출력)
from collections import deque
def dfs(x,y):
q= deque()
dx = [-1, +1]
q.append(x)
while q:
x = q.popleft()
for i in range(3):
if i < 2:
nx = x + dx[i]
elif i == 2:
nx = x * 2
if 0 <= nx < 100001:
if visited[nx] == 0:
visited[nx] = visited[x] + 1
if nx == y:
break
q.append(nx)
if nx == y:
break
start, target = map(int, input().split())
visited = [0] * 100001
visited[start] = 1
dfs(start, target)
print(visited[target] - 1)
- 얻어갈 부분
1. 변형 dx 배열을 선언해서 문제를 풀어봤다
'알고리즘(백준) > BFS & DFS' 카테고리의 다른 글
| [알고리즘/BFS & DFS] 13549번 : 숨바꼭질 3 - python (0) | 2024.02.03 |
|---|---|
| [알고리즘/BFS & DFS] 12851번 : 숨바꼭질 2 - python (0) | 2024.02.02 |
| [알고리즘/BFS & DFS] 2583번 : 영역 구하기 - python (0) | 2024.02.01 |
| [알고리즘/BFS & DFS] 2468번 : 안전 영역 - python (1) | 2024.02.01 |
| [알고리즘/BFS & DFS] 7562번 : 나이트의 이동 - python (0) | 2024.01.31 |