[Swift Algorithm] 숨바꼭질 BOJ #1697

문제 설명

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

 

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

입출력 예제

입력

5 17

출력

4

 

내 문제 풀이

import Foundation

let info = readLine()!.split(separator: " ").map({Int(String($0))!})
var subin = info[0] // 수빈이의 시작점
var target = info[1] // 동생 위치
var queue = [(subin, 0)] // 이동하는 수빈이의 위치와 해당 위치까지 가는데까지 걸린 시간을 튜플로 담음
var found = false // 찾았는지 체크하는 불 변수
var visited = Array(repeating: 0, count: 100001) // 이미 수빈이가 다녀간 자리들을 체크해주기 위함

var index = 0

if subin == target { print(0) } // 처음부터 수빈이와 동생의 위치가 같을 경우 => 바로 끝
else {
    while true {
        let (now, now_count) = queue[index]
        index += 1
        var next = 0 // 수빈이가 이동할 위치를 담을 변수

        for i in 0..<3 {
            if i == 0 { next = now - 1 } // X-1 이동
            else if i == 1 { next = now + 1 } // X+1 이동
            else { next = now * 2 } // X*2 이동
            
            if next < 0 || next > 100000 || visited[next] == 1 { continue } // 예외!
            if next == target { found = true; break } // 찾았을 경우
            visited[next] = 1 // 수빈이가 지나간 곳은 1로 체크헤주기 (같은 곳 또 지나갈 필요 전혀x)
            queue.append((next, now_count + 1)) // 수빈이가 이동할 위치와 그 위치까지 가는데 걸린 시간 추가!
        }
        
        if found { print(now_count+1); break } // 결과 출력
    }
}

👉 bfs문제로, 수빈이가 움직일 수 있는 모든 경로를 탐색해주는게 포인트!

이동하다보면 이미 탐색했던 자리를 중복 탐색하게 되는 경우가 생기는데, 그 예외를 잘 처리해주는것도 중요하다.

• 이 문제는 여러가지 예외가 존재하는데, 첫 번째로 봐줘야 할 예외가 있다.
  처음부터 수빈이와 동생의 위치가 같을 수 있으므로 이 때는 바로 0을 출력하게 했다.
• 그 외의 경우에는 while을 사용해 수빈이의 이동경로를 따라가주었는데,
  이 반복문에서는 수빈이가 갈 수 있는 경로 세 가지 방향을 모두 체크해주고
  갈 수 있는 위치라면 queue에 추가하여 새로 탐색할 시작점을 더해가는 방식으로 구성했다.
• 우선 queue의 형태를 먼저 보면, 튜플형 배열임을 확인할 수 있다. 이렇게 정의한 이유는
  이동하는 수빈이의 위치뿐만 아니라 그 위치까지 가는데 걸린 시간까지 같이 담아주기 위함이다.
• while 반복문 안에서는 index 변수를 이용하여 굳이 queue에서 pop하지 않고 인덱스로 찾아주었다.
  수빈이가 이동할 위치는 next라는 변수에 담아주도록 했다.
  그리고 for문을 활용하여 딱 3번 반복함으로써 수빈이가 갈 수 있는 세 가지 방법을 모두 체크했다.
• 체크하면서 예외 및 수빈이가 동생을 찾았을 경우를 if문으로 처리해주었는데,
  1) next 변수가 0 미만 혹은 100000 초과이거나, 그 자리가 이미 체크했던 곳이라면 continue해주었다.
  이미 체크한 자리인지를 판별하기 위해서는 visited 배열을 만들어 사용해주었다.
  문제에서 주어진 범위만큼의 크기로 배열을 생성하여 지나간 자리는 1을 저장했다.
  2) next 변수가 동생의 위치 target과 같다면 found 변수를 false로 바꾸고 for 반복을 종료하게했다.
  for문이 끝나면 while문 가장 마지막에 found가 true일 때 결과를 출력하고 while반복을 종료하게 했다.
• 위의 두 가지 사항에 해당하지 않을 경우 visited배열을 업데이트하고,
  queue에 (수빈이의 다음 위치, 그 위치까지 걸린 시간)을 추가해주었다.

 

💡 피드백

• 예외만 잘 생각해주면 어렵지 않은 문제였다.
  1) 수빈이와 동생의 위치가 처음부터 같을 경우
  2) 수빈이가 이동할 다음 경로가 0보다 작거나 100000보다 클 경우
  3) 수빈이가 이동할 다음 경로가 이미 체크해줬던 자리일 경우

 

---

문제

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