[실버 3] N과 M (1)

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

15649번: N과 M (1)

저번 스터디 때 쫑나기전 마지막 문제 여서 풀었는데

다시 보니 모르겠다

 

백트래킹 = 전체 순회 dfs가 편함

bfs로는 트리의 깊이가 무한대 일 때 사용 한다

 

import java.io.*;
import java.util.*;

class Main {
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st;

        int N, M;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        boolean[] visited = new boolean[N];

        for(int i =0 ; i< N ; i ++)
            dfs(N, M, visited, i);
    }

    public static void dfs(int N, int M, boolean[] visited, int index) {
        if (visited[index] == true)
            return;

        visited[index] = true;
        sb.append(index+1+" ");

        if(sb.length() == 2*M){
            System.out.println(sb);
            sb.setLength(sb.length()-2);
            visited[index]=false;
            return;
        }

        for (int i = 0; i < N; i++)
            dfs(N, M, visited, i);

        sb.setLength(sb.length()-2);
        visited[index]=false;

    }
}