[Java] 백트래킹 (N과 M (1))

백준에서 N과 M 문제를 오랫동안 봐왔는데 이번 기회에 (1)부터 차례대로 풀어봐야겠다.

 

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

15649번: N과 M (1)

 

 

N과 M이 1부터 8사이이긴 하지만 브루트포스로 돌리면 시간복잡도가 말도 안 되게 높아질 것 같아서 다른 방법으로 풀어야 하는데 문제에 비해 생각보다 풀이법이 떠오르지 않았다. 

 

블로그에서 예전에 풀었던 문제중에 비슷한 걸로 찾아봤더니 DFS를 활용한 백트래킹 문제였다. 내가 가장 못 푸는 문제 유형이니까 이번 기회에 한번 연습해 보자.

 

나는 dfs를 풀 때 배열을 항상 변수명을 graph로 짓기 때문에 다른 의미는 없다.

graph에는 dfs를 돌며 들어가는 숫자들이 담겨있고, visited는 방문 처리용 배열이다. 

 

dfs를 돌면서 깊이가 M이 되면 현재까지의 graph에 저장된 숫자들을 StringBuilder에 저장하고, 돌아와서 visited를 false로 바꿔주는 것이 핵심이다!

 

ㅏ