728x90
반응형
1. 문제 설명
2. 풀이과정
해당 문제는 현재 위치한 점으로부터 이동할 수 있는 경우가 뒤로 1칸, 앞으로 1칸, 순간이동 총 3가지가 있다.
하지만 점 0에서는 더 이상 뒤로 갈 수 없고, 점 100,000에서는 더 이상 앞으로 갈 수 없다.또한 순간이동 시 이동 후 위치가 100,000이 넘어가면 순간이동을 할 수 없다.각 점에서 경우별로 결과를 구하고 이를 그래프로 나타내어 해당 그래프를 BFS 탐색하면 해결할 수 있다.
- sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
- BFS 탐색 함수에서 빠른 연산을 위해 deque 자료구조를 활용하는데 deque 자료구조를 사용하기 위해 deque 모듈을 불러온다. from collections import deque
- 수빈이와 동생의 현재 위치를 입력받는다. N, K = map(int, sys.stdin.readline().split())
- 문제를 해결할 BFS 함수를 생성한다. def bfs(start, end)
- 만약 수빈이가 동생보다 앞에 있다면 수빈이는 뒤로만 갈 수 있으므로 수빈이의 위치에서 동생의 위치까지 거리만큼 이동해야 한다. if (N > K): print(N - K)
- 반면에 수빈이가 동생보다 뒤에 있으면 BFS 탐색을 활용하여 해결해야 한다. else
- 전체 점의 각 점별 이동 최소 시간 정보를 저장할 수 있는 리스트를 생성한다. result = list(0 for _ in range(100001)
- BFS 탐색을 통해 이동 최소 시간을 구하여 출력한다. print(bfs(N, K))
BFS 탐색을 위한 함수
- 각 점별로 가능한 이동 경우의 수를 저장할 deque을 생성한다. queue.deque()
- deque에 초기 시작 위치를 리스트로 추가한다. queue.append([start])
- 이동 시간을 저장할 변수를 생성하고 초기화한다. count = 0
- deque이 공백이 될 때까지 반복한다. while (queue)
- 새로운 시작 위치를 deque에서 꺼내온다. start = queue.popleft()
- 만약 꺼내온 시작 위치 목록에 동생의 위치가 있으면 if (end in start)
- 동생 위치의 이동 시간을 반환한다. return result[end]
- 그게 아니라면 이동을 해야 하므로 이동 시간을 1 증가시킨다. count += 1
- 각 위치별 다음 이동할 수 있는 위치를 저장할 리스트를 생성한다. li = list()
- 꺼내온 시작 위치 리스트의 각 원소를 하나씩 추출하여 for i in start
- 만약 뒤로 1칸 이동할 수 있고 이동한 위치가 처음 이동한 위치라면 if (i - 1 >= 0) and (result[i - 1] == 0)
- 이동한 위치에 이동 시간을 저장하고 result[i - 1] = count
- 이동한 위치를 리스트에 추가한다. li.append(i - 1)
- 만약 앞으로 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)
- 이동 가능한 다음 위치를 모두 구했으면 해당 위치 리스트를 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))
728x90
반응형
'백준' 카테고리의 다른 글
[백준] 15649번 : N과 M (1) - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 (0) | 2023.07.31 |
---|---|
[백준] 11053번 : 가장 긴 증가하는 부분 수열 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 (0) | 2023.07.30 |
[백준] 1436번 : 영화감독 숌 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 (0) | 2023.07.29 |
[백준] 2164번 : 카드2 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 (0) | 2023.07.29 |
[백준] 10845번 : 큐 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 (0) | 2023.07.27 |
[백준] 11653번 : 소인수분해 - 파이썬(Python) - 우당탕탕 개발자되기 프로젝트 (0) | 2023.07.27 |
[백준] 1018번 : 체스판 다시 칠하기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 (0) | 2023.07.26 |
[백준] 1931번 : 회의실 배정 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 (0) | 2023.07.26 |