https://www.acmicpc.net/problem/15649
15649번: N과 M (1)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
이 문제는 처음하는 DFS문제여서 너무 어려웠다....
그래서 결국 다른 사람의 해설을 봤다. DFS와 BFS문제를 여러개 풀어봐야겠다.
원리는 이렇다. 먼저 Int형 배열에 탐색 깊이를 기준으로 index값을 집어 넣는 것이다.
예를 들어보면, N=4, M=2라고 했을 때 N은 요소의 범위이고 M은 깊이이다.
1부터 4에서 1을 골랐을 때 깊이가 2인 수열은 1 2, 1 3, 1 4이다. 즉, 1을 고른 상태에서 다음 수를 고르고 방문을 기록하고 다음 재귀를 통해 방문한 곳은 피하고 방문하지 않은 곳은 방문하는 것이다.
public void dfs(int depth){
if(depth==M){
for(int val : arr){
sb.append(val).append(" ");
}
sb.append("\n");
return;
}
for(int i=0; i<N; i++){
if(!visit[i]){
visit[i] = true;
arr[depth]=i+1;
dfs(depth+1);
visit[i]=false;
}
}return;
}위의 코드처럼 깊이가 M이 되면 출력하고
M이 되기 전이라면 방문확인 리스트에서 확인하는 작업을 수행한다.
여기서 arr는 깊이에 따라 값을 집어 넣는 것이다. 그렇게 깊이가 M이 될때까지 배열을 채우고 M이 되면 배열을 출력하는 것이다.
dfs를 재귀로 호출하고 다시 방문리스트를 초기화하는 것은 1로 시작하는 수열이 끝나고 2로 시작하는 수열이 진행될 때 1 또한 방문할 수 있기 때문이다. 1 2, 1 3, 1 4,2 1,2 3,2 4
i가 0일 때 방문리스트의 index0을 true로 바꾸고 정답 배열에 1을 집어 넣고, 재귀함수에 들어가서 다시 i=0부터 확인하는데 여기서 0은 방문처리 되어있기에 visit = [t,f,f,f]이고, 그래서 재귀함수 안에서 계속 진행하면, [t,t,f,f]로 된다. 그런다음 다시 재귀를 호출하면 이번에는 깊이가 일치하기에 출력하고 재귀가 끝난다. 그럼 다시 그전 단계인 [t,f,f,f]상태로 돌아오고, 그다음인 [t,f,t,f]상태로 가서 또 출력하고 i값은 계속 증가해서 N-1까지 진행하여 [t,f,f,t]까지 나온 후에 다시 맨 처음으로 돌아와서 i=1일 때를 시작한다.
그럼 i=1일 때 [f,t,f,f]의 재귀가 돌기 시작하고, 그럼 [t,t,f,f],[f,t,t,f],[f,t,f,t]가 돌게된다.
그 다음 i=2일 때 [f,f,t,f]의 재귀가 돌아서 [t,f,t,f],[f,t,t,f],[f,f,t,t]가 나오고, i=3이되서 마지막으로 [f,f,f,t]의 재귀가 돌아서, [t,f,f,t],[f,t,f,t],[f,f,t,t]가 된다.
위 코드를 디버깅해보면 쉽게 이해 할 수 있을 것이다.
아직 너무 어려워서 많은 시행착오가 필요할 것같다.