156491 [Swift][DFS][백트래킹] 백준 15649번 (N과 M (1)) 요구능력 : DFS의 응용 코드설명 : DFS를 활용하는 백트래킹 문제이다. 백트래킹이란? 탐색하는데 필요한 많은 자원을 줄이기 위해 유망성있는 노드들을 중심으로 탐색하는 방법이다. 조건을 줘서 필요없는(유망성없는) 노드에는 방문조차 하지않는다. 백트래킹이라는 방법을 사용하기위해 DFS를 이용한다고 생각하면 된다. 이 문제에서 핵심 두 가지다. 1. 수열을 만들되, 백트래킹을 이용하여 중복되는 수(유망성없는 수)를 방문하지 않는다는것이다. 2. DFS를 사용하기 때문에 Stack을 활용한다는 것이다. 문제예시) 4 4를 입력했다고 치자. 아래 코드를 실행하게 되면, result(0) depth = 0, visitied[1] = false -> visited[1] = true, stack = [1] res.. 2021. 9. 23. 이전 1 다음