[백준] (Swift) 1697번 - 숨바꼭질 (실버1, 두가지 풀이 BFS, DP)

오랜만에 포스팅하네용,
이런저런 채용준비때문에 알고리즘을 잘 못풀었던것도 사실이지만, 그동안 푼 알고리즘 문제들은 대부분 파이썬으로 풀기도 했었고 깃허브에만 남기고... 이런저런 이유로 해서 ... 업로드 하지 않았었네요! 하하하하하  다시 화이팅.. ! 🍀

 

⚫️ 문제

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

1697번: 숨바꼭질

 

⚫️ 나의 풀이 (두번째 푸는 것이긴 함!)

문제를 보자마자 생각난 BFS풀이방식이다. 그리고, 문제를 차근차근 생각해보면서, "어 이거 dp로도 풀 수 있겠는데?" 하는 생각이 동시에 들었고, 풀이를 찾아보니까 dp로 푼 사람도 존재했다. 그래서, 두가지 모두 풀이를 해보기로 결정! 

실력이 늘지 않는 것 같아서 속상했는데, 예전에는 실버1도 벅찼지만 요즘에는 그래도 실버1은 자신감을 가지고 숙숙 풀어나간다. 골드 3까지 풀 수 있을정도로 노력해보자! 

1️⃣ 첫번째 풀이, BFS로 풀기

아이패드가 없어서 펜으로 그린거.. 스캔,,,,

bfs는 인접한 노드를 큐에 삽입하면서 최단경로를 찾을 수 있다. 그림으로 그린것처럼, 백준의 첫번째 수빈이의 위치인 5부터 시작하게 되면, 그 인접한 노드들은 5에서 갈 수 있는 위치들이 해당할 것이다. 차근차근 화살표를 그리면서 수빈이의 위치를 큐에 넣어주는 것을 상상했다. 모든 경우를 그리진 않았지만, 결국 우리가 원하는 동생의 위치인 17에 도달할 때, bfs를 탈출하게 해주고, 그때의 depth를 출력하면 최단거리가 될 것이다. 그게 바로 5 -> 10 -> 9 -> 18 -> 17 해서 4가 최단거리가 될 것이다.

이것을 그대로 bfs로 구현했던 1차시도,, 시간초과가 발생했다.

func bfs() {
    let nk = readLine()!.split(separator: " ").map{ Int($0)! }
    var queue = [(nk[0], 0)] // 수빈이의 첫 위치가 시작점, depth 는 0

    while !queue.isEmpty {
        let temp = queue.removeFirst()
        let place = temp.0
        let depth = temp.1

        if place == nk[1] { // k위치면?
            print("\(depth)")
            break
        }

        if place - 1 >= 0 {
            queue.append((place - 1, depth + 1))
        }
        queue.append((place + 1, depth + 1))
        queue.append((place * 2, depth + 1))
    }
}

bfs()

시간초과가 났다. 왜 시간초과가 났을까? 생각했다. while문을 돌리기 때문에, queue의 길이에 다라 시간복잡도는 달라진다. 그래서 큐의 길이인 N이 시간복잡도가 되어 O(N)이 된다. 하지만,,, 내가 여기서 removeFirst()를 사용했다. removeFirst()의 시간복잡도는 O(N),, 그러므로 최종적으로 O(N^2)의 시간복잡도를 갖게된다. 

(그렇다. 우리는 Swift로 bfs를 구현할때, 아주 좋은 성능의 큐 (파이썬의 deque가 없다면, 인덱스로 접근해야한다고 앞서 언급한 적 있다. https://didu-story.tistory.com/422)

우리는 N과 K의 최대값은 10만이고, 각 10만개의 애들이 3개씩의 인접노드를 가지고 있다. 이 모든 노드가 큐에 들어간다치면... 그리고 거기서 또 O(N)의 시간복잡도를 가지는 removeFirst()를 사용하게 되면, 당연스럽게 시간초과가 날 것이다. removeFirst()를 없애고, 시간복잡도 O(1)을 갖는, index로 접근하는 방식으로 시간복잡도를 줄여주어야한다.

그렇게 작성한 2차시도,,,, 메모리 초과가 난다 ㅋㅋㅋㅋㅋㅋ

func bfs() {
    let nk = readLine()!.split(separator: " ").map{ Int($0)! }
    var queue = [(nk[0], 0)] // 수빈이의 첫 위치가 시작점, depth 는 0
    var idx = 0

    while idx <= queue.count {
        let temp = queue[idx]
        let place = temp.0
        let depth = temp.1

        if place == nk[1] { // k위치면?
            print("\(depth)")
            break
        }

        if place - 1 >= 0 {
            queue.append((place - 1, depth + 1))
        }
        queue.append((place + 1, depth + 1))
        queue.append((place * 2, depth + 1))
        idx += 1
    }
}

bfs()

ㅋㅋㅋㅋ 아오 메모리초과... queue에 삽입되는 아이들이 너무 길어져서 그런가? 말그대로 10만개의 아이들에게 3개씩의 인접노드가 있을 테니까... 그래서 queue를 출력해보기로 한다. 

(수빈의 위치, depth) 이렇게 구성됨.. 여기 빨간줄 친것만 보면, 13을 벌써 세번이나 방문한다. 심지어 이것은 큐를 모두 삽입하지 않고, 중간에 아무거나 캡쳐한건데 벌써 세개나 보인다. 세개보다 더 많이 들어있을 것이다.

우리는 '최단거리'를 찾아야한다. 수빈이가 13위치에 도달하는 최단거리는, 무조건 3이다. 그 이상이 되어도 큐에 넣어줄 필요가 없다. 우리는 최단거리만 구해주면 되니까... 그니까 지금 큐에 너무 쓸데없는 것들이 많이 들어있고, 얘네들을 하나씩 전부 접근하면서 메모리초과가 나는게 아닐까? 생각해본다. 그럼 이 모든것들을 visited라는 방문처리 배열을 하나 만들어서 큐에 넣어주지 않는 작업을 해보자.

✅ BFS로 푼 정답코드

위에서 언급한대로, 중복을 줄여주는 visited 배열을 하나 더 만들어서 처리를 해주니까, 통과할 수 있었다.

import Foundation

func bfs() {
    let nk = readLine()!.split(separator: " ").map{ Int($0)! }
    var queue = [(nk[0], 0)] // 수빈이의 첫 위치가 시작점, depth 는 0
    var visited = Array(repeating: false, count: 100001)
    visited[nk[0]] = true
    var idx = 0

    while idx <= queue.count {
        let temp = queue[idx]
        let place = temp.0
        let depth = temp.1

        if place == nk[1] { // k위치면?
            print("\(depth)")
            break
        }

        for i in 0..<3 {
            var nextPlace = 0

            switch i {
            case 0:
                nextPlace = place - 1
            case 1:
                nextPlace = place + 1
            default:
                nextPlace = place * 2
            }

            if nextPlace >= 0, nextPlace <= 100000, !visited[nextPlace] {
                visited[nextPlace] = true
                queue.append((nextPlace, depth + 1))
            }
        }

        idx += 1
    }
}

bfs()

 

2️⃣ 두번째 풀이, DP로 풀기

뭔가, dp로 풀 수 있을 것 같았다. 앞에서 말했듯, 수빈이가 갈 수 있는 place (위치)에 도달할 수 있는 '최단거리'만 구하면 된다. 수빈이는 5부터 시작했으므로, dp[5]에는 5까지 갈 수 있는 최단거리 0을 일단 넣어준다. 여기서부터 생각해보자.

1. 2*x일경우는 dp[짝수]일 경우이다. 즉, dp 내부에서는 짝수일경우와 홀수일경우 두가지로 나눠서 생각이 가능하다.

2. 이동하려고 하는 i가 짝수일 경우를 살펴보자. 만약 5에서 12까지 이동한다면?  dp[i]까지 가는 방식은 아래 연두색과 하늘색 두가지 방식으로 갈 수 있다. 11에서 오거나, 6에서오거나!! 둘중하나가 최단거리가 될 수 있다. 현재는 거리가 짧으므로, 무조건 짝수에서 오는게 최단거리 아니야? 싶을 수 있겠지만, 우리는 범위 10만을 다룰 것이기 때문에, 두가지 경우중 작은 것을 넣어주자.

그렇기 때문에 i 가 짝수일 경우에, dp[i] = dp[i/2] + 1 이거나 한 칸 전 (11)에서 온 경우가 최소일 수도 있으니 두개를 비교해서 넣어주자.

 

3. i가 홀수일 경우를 살펴보자. 아래 그림에서는 세개의 선을 그려놓았지만, 어찌됐든 요약해보면 13까지 오는 경우의 수는 12에서 오거나, 14에서 오거나 둘중 하나이다. 하지만 12와 14는 모두 짝수이기에, 12/2 나, 14/2에서 온 값들로 채워져 있을 것이다. 그럼 그것들에서 +1 해준 값이 홀수까지 오는 최단거리가 된다.

그림에도 쓰여져 있지만, 주의할점이 있다. dp는 앞에서부터 채워나가니까, dp[13]을 채울 때, dp[14]는 존재하지 않는다. (아니면 처음 초기화된 temp값 아무거나로 채워져있을 것이다.) 이것으로 값을 갱신해줄 수 없으니, dp[14]에 오게 될 값 dp[7]의 값에서 +1 해준 값을 넣어준다.

4. 그리고 주어진 수빈이의 위치보다 앞에있는 애들은 전부 -1씩 넣어준다. 예시로보면 5부터 시작이고, dp[4]는 5-4인 1이 들어갈 것이고, dp[3]은 2, dp[2]는 3... 이렇게 들어갈 것이다. (앞으로 가는 방법은 한칸씩 움직이는 방법밖에 없기 때문!
그렇다면, dp를 먼저 채워주고 시작해야겠지?

이 모든 것들을 구현하고 코드를 돌렸는데, 1차시기 전부 틀렸다.

import Foundation

func dp() -> Int {
    let nk = readLine()!.split(separator: " ").map{ Int($0)! }
    var dp = Array(repeating: 100001, count: 100001) // 최대값아무거나로 채워줌

    if nk[0] >= nk[1] {
        return nk[0] - nk[1]
    }

    for i in 0..<nk[0] {
        dp[i] = nk[0] - i
    }

    for i in nk[0]+1...nk[1] {
        if i % 2 == 0 {
            // 짝수이면
            dp[i] = min(dp[i/2] + 1, dp[i-1] + 1)
        } else {
            // 홀수이면
            dp[i] = min(dp[i-1] + 1, dp[(i+1)/2] + 2)
        }
    }

    return dp[nk[1]]
}

print(dp())

진짜 뭐가 틀린거야 ㅋㅋㅋㅋㅋㅋㅋ 

고민고민하다가 유심히 범위를 살폈다. 지금.... n과 k가 같을 경우를 처리해주지 않았다. 같은경우에는 dp에 0을 넣어주어야한다. 이거찾느데만 몇분이 걸린거야 ㅠㅠㅠ 

✅ 그래서 맞춘 최종코드!

import Foundation

func dp() -> Int {
    let nk = readLine()!.split(separator: " ").map{ Int($0)! }
    var dp = Array(repeating: 100001, count: 100001) // 최대값아무거나로 채워줌

    if nk[0] >= nk[1] {
        return nk[0] - nk[1]
    }

    for i in 0..<nk[0] {
        dp[i] = nk[0] - i
    }
    
    dp[nk[0]] = 0

    for i in nk[0]+1...nk[1] {
        if i % 2 == 0 {
            // 짝수이면
            dp[i] = min(dp[i/2] + 1, dp[i-1] + 1)
        } else {
            // 홀수이면
            dp[i] = min(dp[i-1] + 1, dp[(i+1)/2] + 2)
        }
    }

    return dp[nk[1]]
}

print(dp())

 

아오 .. 드디어 맞았다.

사소한 범위실수, 그리고 'n과 k가 같을경우', 그리고 'n이 k보다 클 경우'를 처리해주지 않아서 풀이방법은 전부 다 생각해놓았지만,,,,, 이런것들때문에 오래걸렸다 ㅠㅠ 하.... 이런 잔실수를 줄이기 위해서 노력해야겠다.... 결국 dp도 그래서 뭘 놓쳤는지 찾아보기 위해서 다른 풀이를 참고했다 ㅠㅠㅠㅠㅠ 아 진짜!! 제발 잔실수하지말고 정신 똑바로 차리고 해야겟다!