[알고리즘/BFS & DFS] 1697번 : 숨바꼭질 - python

링크 : https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

---

• 문제
• 소요시간: 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 배열을 선언해서 문제를 풀어봤다