-
[Python 3] BOJ - 1697 "숨바꼭질"BOJ 2020. 6. 25. 10:42
# 문제 링크 : https://www.acmicpc.net/problem/1697
# 풀이 :
개인적으로 이 문제의 핵심은 BFS라고 생각한다. 비록 문제에 직접적으로 그래프는 없지만 BFS형식으로 풀 수 있다. BFS/DFS의 핵심은 정점을 한번만 방문하는 것이다. 그런데 이 문제에서 만일 2초 후 위치가 7이 된다고 가정하자. 그런데 또 5초 후 위치가 7이라면 이는 방문하지 않아도 된다. 왜냐하면 만일 동생의 위치가 7이라면 2초 후에 만나면 사실 5초 후에 만나는 것은 의미가 없기 때문이다. 또한 만일 동생의 위치가 7이 아니라고 해도 7을 두번 방문하는 것은 의미가 없다. 왜냐하면 계속 7을 방문해도 동생은 없기 때문이다. 따라서 큐가 빌 때 까지 계속 POP한 후 현재 위치에서 갈 수 있는 세가지 위치(+1, -1, *2)를 방문하지 않았다면 방문 배열에 방문 여부를 바꾸고 큐에 바뀐 위치를 넣는다. 한번 간 곳은 다시 가지 않으므로 큐가 POP할 때 위치가 동생의 위치가 같다면 그 때 시간을 출력하면 정답을 구할 수 있다.
# 코드
import sys, collections # check : num이 문제의 범위를 만족하는 검사하는 함수 def check(num): if 0 <= num <= 100000: return True else: return False # MAX : 문제의 상한값 MAX = 100001 # visited : 방문 배열 vistied = [False] * MAX # 입력부 me, sibling = map(int, sys.stdin.readline().split()) q = collections.deque() # 초기위치 방문 및 큐에 삽입 vistied[me] = True q.append((me, 0)) while q: # loc : 현재 위치, time : 현재 위치의 시간 loc, time = q.popleft() # 현재 위치와 동생의 위치가 같다면 정답 출력 후 종료 if loc == sibling: print(time) break # 현재 위치 + 1이 범위에 있다면 if check(loc + 1): # 현재 위치 + 1이 한번도 방문하지 않았다면 if vistied[loc + 1] == False: # 방문 후 큐에 삽입 vistied[loc + 1] = True q.append((loc + 1, time + 1)) # 현재 위치 - 1이 범위에 있다면 if check(loc - 1): # 현재 위치 - 1이 한번도 방문하지 않았다면 if vistied[loc - 1] == False: # 방문 후 큐에 삽입 vistied[loc - 1] = True q.append((loc - 1, time + 1)) # 현재 위치 * 2가 범위에 있다면 if check(2 * loc): # 현재 위치 * 2가 한번도 방문하지 않았다면 if vistied[2 * loc] == False: # 방문 후 큐에 삽입 vistied[2 * loc] = True q.append((2 * loc, time + 1))
'BOJ' 카테고리의 다른 글
[Python 3] BOJ - 1707 "이분 그래프" (0) 2020.07.08 [Python 3] BOJ - 1701 "Cubeditor" (2) 2020.07.08 [Python 3] BOJ - 1689 "겹치는 선분" (0) 2020.06.24 [Python 3] BOJ - 1688 "지민이의 테러" (0) 2020.06.23 [Python 3] BOJ - 1658 "돼지 잡기" (0) 2020.06.01