[Swift][백준 알고리즘] 15649 N과 M (1)

문제:    

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

15649번: N과 M (1)

 

풀이방법:    

💡 배열(스택)과 재귀을 이용해서 DFS 구현

 

DFS? 재귀? 배열(스택)? 우선 차근차근 알아가보자.

 

DFS

링크의 예제 3을 예시로 다뤄보려 한다.

빨강)

1로 첫번째 자리가 고정되었을 때 두번째 자리의 값이 2, 3, 4 이렇게 숫자가 바뀌는 것을 알 수 있다.

두번째 자리가 2로 시작하는 모든 경우의 수를 찾은 후에 두번째 자리의 값은 3으로 바뀐다.

파랑)

이 과정은 모든 자리수에서 마찬가지이다. 

첫번째 자리에 1이 존재할 때 찾을 수 있는 모든 경우의 수를 출력하면, 그 후에는 첫번째 자리의 수가 2로 시작하게 된다.

사용자의 입력 값

4 4

출력값

1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 ...

이렇게 한 숫자로 뻗어나가는 가지를 모두 탐색하고 다시 한 숫자로 돌아오는 기법을 DFS라고 한다.

우리말로는 깊이 우선 탐색이라고 하는데, 그림을 보면 알겠지만, A-> B-> C 이렇게 옆으로 나아가는 게 아니라

A-> B -> D -> H 이렇게 아래로 나아가는 방법이라해서 붙어진 이름이다.

https://velog.io/@chayezo/%EA%B9%8A%EC%9D%B4-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89DFS-Depth-First-Search

 

스택과 재귀

이러한 DFS는 스택과 재귀를 통해서 구현해 나갈 수 있다.

본 내용은 글로 설명하는 것보다 코드와 그림을 보며 이해하는 게 직관적일 거라 생각한다.

해당 그림은 5(N) 4(M)가 입력되었을 때를 기준으로 처음 시작 부분부터 1245가 나올 때까지 일부만 그려보았다.

 

좌측에 recursivefunc 박스는 호출되는 재귀함수가 스택에 쌓이는 모습을 나타내었고, 

우측의 숫자가 쌓이는 통은 resultArray를 그린 것이다. ( 아래에서부터 index 0 )

 

그림을 보면 주황색 재귀함수가 끝나고 나서 노란색 재귀함수에서 주황색 재귀함수를 호출했던 부분 이후부터 다시 시행이 되는 것을 확인 할 수 있다.

이 점은 DFS에서 밑 바닥까지 확인했을 경우 윗 가지로 올라가 다시 아래로 내려가는 것과 유사하다.

 

 작성한 코드는 다음과 같다. 

import Foundation

let nums = readLine()!.split(separator: " ").map {Int(String($0))!}
let N = nums[0]
let M = nums[1]

var resultArray : [Int] = []
var existenceArray = Array(repeating: false, count: N)

recursiveFunc()

func printArray(){
    print(resultArray.map({String($0)}).joined(separator: " "))
}

func recursiveFunc(){
    
    if(resultArray.count == M){
        printArray()
        return
    }
    
    for i in 1...N{
        if(!resultArray.contains(i)){
            resultArray.append(i)
            recursiveFunc()
            resultArray.popLast()
        }
    }
}

 

 

성공한 사진!    

 

  MEMO 

자료구조와 컴퓨터 구조 수업에서 배웠던 부분이 나와서 반가웠다. 그때는 진짜 너무 힘들었었는데 지금은 조금만 생각해도 이해가 되는 게 신기했다. 다만 코드를 내 머릿속에서 구조화 되어 나왔던 것이 아니라 다른 사람들의 코드를 보고 감을 잡아갔던 게 좀 아쉬웠던 것 같다. 이런 부류의 문제가 나오면 재귀와 스택을 이용해서 DFS를 구현하자 ! 라고 생각을 할 수 있길!

+ 인간은 망각의 동물이라고,,사실은 DFS가 뭔지 잠시 까먹어서 다시 찾아봤었다.. 꾸준히 계속 사용해보자,, 화이팅,,

+ 설명을 하기 어려워서 그림으로 퉁쳤던 게 좀 아쉽다.. 개발자 답게 설명할 줄 아는 능력도 키워나가보자.