문제
✔ 난이도 - Silver 3
설명
숫자는 중복없이 고르고, 순서가 있는 조합(순열)이다.
백트래킹 : DFS(깊이 우선 탐색 - 재귀함수 사용) + 방문여부 체크
💡백트래킹에서는 선택 -> 재귀 -> 선택취소(복구)가 핵심 패턴!
result는 M개의 선택한 순열을 담을 int 배열
visited는 방문여부를 저장할 boolean 배열
풀이
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] result = new int[M]; // 0 ~ (M - 1)
boolean[] visited = new boolean[N + 1]; // 1 ~ N
//깊이 0부터 시작
dfs(N, M, 0, result, visited);
System.out.println(sb);
}
public static void dfs(int N, int M, int depth, int[] result, boolean[] visited){
if (depth == M){
// M개의 숫자 다 고르면 출력
for (int i = 0; i < M; i++){
sb.append(result[i] + " ");
}
sb.append("\n");
return;
}
for (int i = 1; i <= N; i++){
// 아직 그 숫자가 사용이 안됨
if (!visited[i]) {
result[depth] = i;
visited[i] = true;
dfs(N, M, depth + 1, result, visited); //다음 숫자 뽑으러 감
visited[i] = false; //백트래킹 (원상복구)
}
// return;
//이 return문이 있으면 result[0]에 1을 넣고나서 visited[1] 을 true로 만들고나서 dfs을 한 번 더 타면
// result[1]을 검사하게되는데 이미 1은 true니까 if문에 안걸리고
// 바로 return돼서 visited[1] 을 false로 만들고나서 main함수로 리턴돼서 그대로 끝남.
}
}
}TIL💡
📌 StringBuilder를 static으로 선언한 이유
static StringBuilder sb = new StringBuilder();
Java 프로그램의 시작점인 main() 메서드는 static이다.
main() 함수 안에서 직접 사용하는 변수는 static일 필요는 없지만(자기 스코프 내의 변수니까)
main() 밖의 메서드나 전역적으로 공유하려면 static이거나 파라미터를 통해 전달해야한다. 파라미터 사용 : 객체지향적으로 더 깔끔함!
정리하자면,
static 메서드 안에서 클래스의 non-static 필드나 클래스의 non-static 메서드를 직접 사용하려고 하면 오류가 발생한다!
public class Test {
int num = 42; // non-static 필드
public static void main(String[] args) {
System.out.println(num); // ❌ 오류: Cannot make a static reference to the non-static field 'num'
}
}| 항목 | static(정적) | non-static(인스턴스) |
|---|---|---|
| 소속 | 클래스 자체에 소속 | 객체(인스턴스)에 소속 |
| 사용 시점 | 클래스를 만들자마자 사용 가능 | 객체를 생성해야 사용 가능 |
| 메모리 위치 | 클래스가 로드될 때 할당 | 객체가 생성될 때마다 새로 할당 |
따라서 코드에서 dfs() 함수도 static으로 선언하였음.
dfs() 함수에서 N, M, depth, result, visited는 파라미터를 통해 넘겨주었기때문에 static을 붙이지 않음.
그러나 StringBuilder sb는 main과 dfs에서 둘 다 쓰기 위해서 전역적으로 선언해주었고,(dfs는 재귀적으로 여러번 호출된다. Stringbuilder를 지역변수로 만들면 매번 초기화되어 누적되지 않음. 따라서 한 번만 선언되고 모든 재귀 호출에서 공유되는 전역변수인게 좋다.) main과 dfs 메서드는 static으로 선언된 메서드이기 때문에 static으로 선언해주었다.
