[백준] 5014.스타트링크 (Swift)

[백준] 5014.스타트링크 (Swift)

https://www.acmicpc.net/problem/5014

5014번: 스타트링크

풀이

시작층에서 목표층까지 도달하기 위해 버튼을 눌러야하는 최소 횟수를 구해야 합니다.

 

버튼은 위, 아래 2개가 존재하기 때문에 현재 있는 층에서 위로 가는 버튼을 누른다, 아래로 가는 버튼을 누른다 2가지 경우의 수를 생각해볼 수 있습니다.

 

이렇게 생각하면 간단하게 구현할 수 있을 것 같지만, 신경써야 하는 점이 크게 2가지가 있습니다.

 

이미 방문한 층에서는 어떤 선택을 하던 이전의 경우와 똑같은 수가 나올 것이니 이를 처리해줄 필요가 있습니다. 저는 이를 위해 visited 라는 Set 을 선언하여 방문한 층수를 기록해두었습니다.

 

건물의 총 층수가 정해져있기 때문에 해당 값을 넘지 않도록 하며, 0 이하로 건물의 층수가 작아지는 일은 없을테니 이 또한 고려해주어야 합니다.

 

이 점에 유의하여 큐에 방문할 수 있는 경우의 수를 집어넣고 BFS 와 같은 원리로 차례차례 탐색해보면 목표층에 도달하기 위한 최소횟수를 구할 수 있습니다.

 

이는 모든 경우의 수를 탐색하는 과정과 비슷합니다. 그렇기 때문에 목표층에 도달할 수 있다면 BFS 함수는 무조건 중간에 종료됩니다.

 

반대로 생각했을때 BFS 함수가 모든 경우의 수를 탐색했는데도 종료되지 않는다면, 목표층에 도달할 수 없다는 뜻입니다. 

코드