백준 1697,12851,13913 파이썬 풀이 (숨바꼭질 1, 숨바꼭질 2, 숨바꼭질 3)

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

위 문제 3개는 공통적으로 수빈이와 동생이 숨바꼭질을 하는 것을 전제로 한다.

 

문제 1.

수빈이는 1초 후 X + 1, X - 1, 2X 의 위치로 이동할 수 있다. 수빈이가 동생을 찾는 가장 빠른 시간을 출력해야 한다.

 

해결방법

1. BFS를 통해서 처음 위치에서 이동 가능한 모든 위치들을 큐에 넣어가며 탐색을 시작한다.

2-1. 이동한 위치에 동생이 없으면 현재 위치에서 [X + 1, X -1, 2X]중 조건을 만족하는 다음 위치들을 큐에 넣는다. 현재 위치까지 걸린 시간을 이전 위치에서의 시간 + 1로 지정한다.

2-2. 이동한 위치에 동생이 있다면 현재 위치에서의 시간을 출력하고 종료한다. 너비 우선 탐색을 진행했고, 다음 위치로 이동하는 시간이 모두 1초로 동일하기 때문에 (- 가중치가 똑같기 때문에 ) 반복문에서 가장 먼저 도착한 경우의 시간값이 곧 최소 시간이다.

 

코드

#BOJ 1697 - 숨바꼭질
from collections import deque

spos,bpos = map(int,input().split())
queue = deque()
time = [0] * 100001

queue.append(spos)
while queue:
    curpos = queue.popleft()
    if curpos == bpos:
        print(time[curpos])
        break
    for nextpos in [curpos - 1,curpos + 1,curpos * 2]:
        if nextpos > -1 and nextpos < 100001 and time[nextpos] == 0:
            queue.append(nextpos)
            time[nextpos] = time[curpos] + 1

문제 2.

수빈이는 1초 후 X + 1, X - 1, 2X 의 위치로 이동할 수 있다. 수빈이가 동생을 찾는 가장 빠른 시간을 출력하고, 이 방법이 몇가지인지 출력해야한다.

 

해결방법

1. 문제 1과 같이 탐색을 시작한다.

2-1. 이동한 위치에 동생이 없다면 이동 가능한 다음 위치들에 대해서

          1. 범위 내에 있는지

          2. 방문하지 않은 구역이거나, 방문했어도 현재 경우의 수로 걸리는 시간보다 크거나 같을때

                                                (최단 시간으로 갱신 및 최단 시간의 다른 경로를 큐에 넣어 cnt를 추가하기 위해)

       위 조건들을 만족할 때 시간값을 갱신 및 큐에 넣는다.

2-2. 이동한 위치에 동생이 있을 시, cnt를 1 추가한다.

3. 항상 최단시간이 갱신되며 cnt를 추가했으므로 time[bpos] 가 최단 시간이다. 이를 출력해준다.

 

코드

#BOJ 12851 - 숨바꼭질 2
from collections import deque

spos,bpos = map(int,input().split())
queue = deque()
time = [-1] * 100001
time[spos] = 0
queue.append(spos)
cnt = 0
while queue:
    curpos = queue.popleft()
    if curpos == bpos:
        cnt += 1
    for nextpos in [curpos - 1,curpos + 1,curpos * 2]:
        if nextpos > -1 and nextpos < 100001 and (time[nextpos] == -1 or time[nextpos] >= time[curpos] + 1):
            queue.append(nextpos)
            time[nextpos] = time[curpos] + 1

print(time[bpos])
print(cnt)

 

문제 3.

수빈이는 1초 후 X + 1, X - 1, 0초 후에 2X 의 위치로 이동할 수 있다. 수빈이가 동생을 찾는 가장 빠른 시간을 출력하고, 이 방법이 몇가지인지 출력해야한다.

 

해결방법

1. 문제 1과 같이 탐색을 시작한다.

2. 순간이동은 0초가 걸리므로 순간이동이 무제한으로 가능하다고 보고 항상 큐의 앞에 넣어줘야 한다. deque의 appendleft()를 사용해서 큐의 앞으로 이동 가능한 좌표들을 보내준다. 

3. 동생을 찾으면 걸린 시간을 출력하고 종료한다.

 

코드

#BOJ 13549 - 숨바꼭질3
from collections import deque

spos,bpos = map(int,input().split())
queue = deque()
time = [-1] * 100001
time[spos] = 0
queue.append(spos)
while queue:
    curpos = queue.popleft()
    if curpos == bpos:
        print(time[curpos])
        break
    for nextpos in [curpos - 1,curpos + 1,curpos * 2]:
        if nextpos > -1 and nextpos < 100001 and time[nextpos] == -1:
            if nextpos == curpos * 2:
                time[nextpos] = time[curpos]
                queue.appendleft(nextpos)
            else:
                time[nextpos] = time[curpos] + 1
                queue.append(nextpos)