dfs 조합이해하기

https://school.programmers.co.kr/learn/courses/30/lessons/42890

프로그래머스

 

이문제를 푸는데 dfs를 이용하려 했다 그러나 

그래서 기존 코드를 가져왔는데 뜻대로 작동하지 않았다

예를들어 1234 이면 기존 내가 터득한 dfs는

1234 1243이 별개이다 그러나 이문제는 1234 1243을

같은걸로 봐야했다 그래서 gpt에게 물어보니 내가 배워왔던 dfs는 

순열이고 조합은 다른거라고 했다 그래서 코드로 익히니

public static void dfs(boolean[] visited, int[] selectedCols,int start) {

        System.out.println(Arrays.toString(visited));    

        for (int i = start; i < visited.length; i++) {

            if (!visited[i]) {

                visited[i] = true;

                System.out.println("자식 시작: " + i);

                dfs(visited, selectedCols,i+1);

                visited[i] = false;

                System.out.println("백트래킹: " + i+Arrays.toString(visited));

            }

        }

    }

저 내부 for문에 start를 할당량을 해줘야 한다고 한다.

gpt 고맙다 코테에서 제일 어려운게 반복을 해야하는데 for문 개수가

정해져 있지 않을때 인데 순열과 조합을 잘외워서 적절하게 써야겠다

 

*9월15일 추가*

일반적인 조합 DFS 방식이면 visited 없어도 돼.

start 인덱스를 넘겨서 앞으로만 선택하게 만들면 중복 선택을 막을 수 있어.

즉 예제 소스의 visited는 필요없다

 

근데 그래도 어렵다 문제가 다시 풀어봐야겠다