[백준/JAVA] 백트래킹 15649 N과 M(1)

나의 답) 틀림

import java.io.*;
import java.util.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (i == j) continue;
                else sb.append(i).append(" ").append(j).append(" ");
            }
            sb.append("\n");
        }
        
        System.out.print(sb);
    }
}

 

입력:

N = 4, M = 2

 

의도한 출력:

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

 

실제 출력:

1 2 
2 1 
3 1 3 2 
4 1 4 2

 

 

틀린 이유

• 내부 for문이 j를 1부터 M까지 반복하므로 N = 4, M = 2에서 j의 범위가 제대로 설정되지 않았다.
• i == j 조건에서 j의 범위를 M으로 제한한 것이 의도한 순열을 방해했다.

 

수정된 답) 288ms

import java.io.*;
import java.util.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        int[] res = new int[m];
        boolean[] visited = new boolean[n + 1];
        
        backtrack(n, m, 0, res, visited, sb);
        
        System.out.print(sb);
    }
    static void backtrack(int n, int m, int depth, int[] res, boolean[] visited, StringBuilder sb) {
        if (depth == m) {
            for (int i = 0; i < m; i++) {
                sb.append(res[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                res[depth] = i;
                backtrack(n, m, depth + 1, res, visited, sb);
                visited[i] = false;
            }
        }
    }
}