[백준 1697번] 숨바꼭질

난이도: 실버 I

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

1697번: 숨바꼭질

백준 1697번 문제 숨바꼭질

한동안 면접 준비하고 교육 받느라 알고리즘에 뜸했던 탓인지 좀 어려운 문제를 못 풀겠어서 (ㅠㅠ)

비교적 간단한 실버1 문제를 풀어 봤습니다.

 

출발점 n에서 도착점 k까지의 도달 최단 시간을 구하는 문제입니다.

n에서 이동은 [n - 1, n + 1, n * 2] 세 가지만 가능하며, 각 이동은 1초가 소요됩니다.

따라서 탐색 알고리즘을 이용하면 쉽게 풀 수 있으며, 저는 BFS를 이용하였습니다.

 

visited 배열에 아직 방문하지 않은 위치의 도착 시간은 무한 (INF)으로 설정하고, 시작점은 0으로 설정합니다.

이동하려는 곳의 도착 시간이 현재 위치의 도착시간 + 1보다 크면, 이동하려는 곳의 도착 시간을 현재 위치의 도착시간 + 1으로 갱신하고, 이동하려는 곳을 queue에 넣습니다.

편의성을 위해 이동하는 위치가 범위 내에 있는지 검사하는 in_boundary 함수, n에서 이동하는 경우를 return하는 move 함수 등을 별도로 작성하여 사용하였습니다.

 

코드 (C++, Java):

 

채점 결과