[백준] 1697번 : 숨바꼭질 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1697번: 숨바꼭질

 

1. 문제 설명

2. 풀이과정

해당 문제는 현재 위치한 점으로부터 이동할 수 있는 경우가 뒤로 1칸, 앞으로 1칸, 순간이동 총 3가지가 있다.

하지만 점 0에서는 더 이상 뒤로 갈 수 없고, 점 100,000에서는 더 이상 앞으로 갈 수 없다.또한 순간이동 시 이동 후 위치가 100,000이 넘어가면 순간이동을 할 수 없다.각 점에서 경우별로 결과를 구하고 이를 그래프로 나타내어 해당 그래프를 BFS 탐색하면 해결할 수 있다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. BFS 탐색 함수에서 빠른 연산을 위해 deque 자료구조를 활용하는데 deque 자료구조를 사용하기 위해 deque 모듈을 불러온다. from collections import deque
3. 수빈이와 동생의 현재 위치를 입력받는다. N, K = map(int, sys.stdin.readline().split())
4. 문제를 해결할 BFS 함수를 생성한다. def bfs(start, end)
5. 만약 수빈이가 동생보다 앞에 있다면 수빈이는 뒤로만 갈 수 있으므로 수빈이의 위치에서 동생의 위치까지 거리만큼 이동해야 한다. if (N > K): print(N - K)
6. 반면에 수빈이가 동생보다 뒤에 있으면 BFS 탐색을 활용하여 해결해야 한다. else
7. 전체 점의 각 점별 이동 최소 시간 정보를 저장할 수 있는 리스트를 생성한다. result = list(0 for _ in range(100001)
8. BFS 탐색을 통해 이동 최소 시간을 구하여 출력한다. print(bfs(N, K))

BFS 탐색을 위한 함수

1. 각 점별로 가능한 이동 경우의 수를 저장할 deque을 생성한다. queue.deque()
2. deque에 초기 시작 위치를 리스트로 추가한다. queue.append([start])
3. 이동 시간을 저장할 변수를 생성하고 초기화한다. count = 0
4. deque이 공백이 될 때까지 반복한다. while (queue)
5. 새로운 시작 위치를 deque에서 꺼내온다. start = queue.popleft()
6. 만약 꺼내온 시작 위치 목록에 동생의 위치가 있으면 if (end in start)
7. 동생 위치의 이동 시간을 반환한다. return result[end]
8. 그게 아니라면 이동을 해야 하므로 이동 시간을 1 증가시킨다. count += 1
9. 각 위치별 다음 이동할 수 있는 위치를 저장할 리스트를 생성한다. li = list()
10. 꺼내온 시작 위치 리스트의 각 원소를 하나씩 추출하여 for i in start
11. 만약 뒤로 1칸 이동할 수 있고 이동한 위치가 처음 이동한 위치라면 if (i - 1 >= 0) and (result[i - 1] == 0)
12. 이동한 위치에 이동 시간을 저장하고 result[i - 1] = count
13. 이동한 위치를 리스트에 추가한다. li.append(i - 1)
14. 만약 앞으로 1칸 이동할 수 있고 이동한 위치가 처음 이동한 위치라면 if (i + 1 <= 100000) and (result[i + 1] == 0)
15. 이동한 위치에 이동 시간을 저장하고 result[i + 1] = count
16. 이동한 위치를 리스트에 추가한다. li.append(i + 1)
17. 만약 순간이동할 수 있고 이동한 위치가 처음 이동할 위치라면 if (i * 2 <= 100000) and (result[i * 2] == 0)
18. 이동한 위치에 이동 시간을 저장하고 result[i * 2] = count
19. 이동한 위치를 리스트에 추가한다. li.append(i * 2)
20. 이동 가능한 다음 위치를 모두 구했으면 해당 위치 리스트를 deque에 추가한다. queue.append(li)

반응형

3. 소스코드

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())

def bfs(start, end):
    queue = deque()
    queue.append([start])

    count = 0
    while (queue):
        start = queue.popleft()
        if (end in start):
            return result[end]

        count += 1
        li = list()
        for i in start:
            if (i - 1 >= 0) and (result[i - 1] == 0):
                result[i - 1] = count
                li.append(i - 1)

            if (i + 1 <= 100000) and (result[i + 1] == 0):
                result[i + 1] = count
                li.append(i + 1)

            if (i * 2 <= 100000) and (result[i * 2] == 0):
                result[i * 2] = count
                li.append(i * 2)

        queue.append(li)

if (N > K):
    print(N - K)
else:
    result = list(0 for _ in range(100001))
    print(bfs(N, K))