[Swift] - 경로탐색

스위프트로 경로를 탐색해보자

1. 문제 설명

입력값 : [[n, m]] , max

n --- > m 경로로 넘어갈 수 있다.
max 는 [n, m] 배열중 가장 큰 수이다.

예로
[1,2][1,3][1,4][2,1][2,3][2,5][3,4][4,2][4,5]

max 는 5로 주어진다.

1에서 max 로 갈 수 있는 경로의 수를 구하라.

2. 나의 풀이

import Foundation

func solution(_ route: [[Int]], _ maxNum: Int) {
    var procession: [[Int]] = Array(repeating : (Array(repeating: 0, count: maxNum+1)), count: maxNum)
    for road in route {
        procession[road[0]][road[1]] = 1
    }
    var lv: Int = 1
    var cnt: [Int] = Array(repeating: 0, count: maxNum + 1)
    cnt[0] = 1
    cnt[1] = 1
    var show: [Int] = [1]
    func D(_ n: Int) {
        if n == maxNum {
            print(show)
        } else if lv == maxNum { 
            print(show)
        } else {
            for i in 2...maxNum {
                if cnt[i] == 0 && n != i && procession[n][i] == 1 {
                    lv += 1
                    cnt[i] = 1
                    show.append(i)
                    D(i)
                    lv -= 1
                    cnt[i] = 0
                    show.removeLast()
                }
            }
        }
    }
    D(1)
}

3. 풀이 설명

굉장히 어려운 문제다. 나는 DFS를 이용해서 풀었다.

DFS를 응용해보자.

일단 이번 문제는 1로 시작한다. 1에서 maxNum 으로 가는 경우의 수를 구해야하기 때문.

하지만 나의 cnt 배열의 index 는 0 부터 시작하고, 우리가 사용 가능한 숫자는 2 부터 maxNum 이고, 행렬을 만들어보면 역시 index = 0 부터 시작하고, 내 머리를 깨버리려고 작정한 것 같았다.
그래서 아예 처음부터 직관적으로 만들어버리기로 했다.

행렬을 maxNum x maxNum 이 아닌, maxNum + 1 x maxNum 로 만들었다.
어떻게되냐면 ( 위 예제를 예로 들어보자 )
1 1 1 1 0
1 1 1 0 1
0 0 1 1 0
0 1 0 1 1
0 0 0 0 1

로 짠 maxNum x maxNum 이 아니라.

0 0 0 0 0 0
0 1 1 1 1 0
0 1 1 1 0 1
0 0 0 1 1 0
0 0 1 0 1 1

로 maxNum x maxNum+ 1 로 짠다

이게 가능한 이유는 어짜피 5, n 이 없고, 5에 도착하면 루프가 끝나야 하기 때문.

이렇게 행렬을 짜면 또 좋은 점은 인덱스를 줄이거나 늘리거나 할 필요없이 그냥 집어 넣으면 된다.
또, cnt[] 를 어떻게 놓냐면,

cnt = [1,1,0,0,0,0] 으로 놓는다.

우리는 0 과 1 은 사용할 필요가 없기 때문에 사용할 2 부터 5 까지
cnt[2] ~ cnt[5] 만 1로 놓는다.

cnt 역시 인덱스를 늘리거나 줄이거나 할 필요없이 그대로 사용하면된다.