백준 15650번 : N과 M(2) (JAVA) 문제 풀이

www.acmicpc.net/problem/15650

15650번: N과 M (2)

---

 

 

 

문제 분석

저번 N과 M(1) 에서 살짝 변형이 된 문제다.

예제를 먼저 살펴보면

예제 입출력 2

자연수의 범위는 4이고, 2개씩 출력시키면 되는데,

같은 수가 중복되서 연속되면 안되고, 수열도 중복이 되면 안된다. (예를 들어, [1 2] 와 [2 1]은 같다고 본다.)

 

실행 과정

for( i가 1일때) 재귀 호출하여 자식 노드들을 방문 하고 있다.

그림처럼, arr[0]에 for문으로 돌면서 i값을 넣어주고, 다음 arr[1]값은 재귀 호출을 돌면서 채우는 식으로 진행된다.

이 실행 과정을 코드로 나타내면,

static int N, M;

public static void main(String[] args){

	// N, M 입력
    
    dfs(0); // 0부터 시작!
}

static void dfs(int index) {
	
    for(int i=1; i<=N; i++) {
    	arr[i] = i;		// 현재 인덱스에 값을 넣어주고
        visit[i] = true;	// 방문 여부 체크
        dfs(index + 1); 	// 다음 인덱스 채우기 위해 다시 재귀호출!
    }
}

 

i가 2가 될 때, visit의 값은 visit[1]만 true로 바뀌어야 한다.

static void dfs(int index) {
	
    for(int i=1; i<=N; i++) {
    	arr[i] = i;		
        visit[i] = true;
        dfs(index + 1);
        
        /* 재귀 호출이 끝난 후에 현재 i만 true로 바꾸고 나머지는 false로 해준다. */
        for(int j=i+1; j<=N; j++) {
        	visit[j] = false;
        }
    }
}

 

 

종료 조건

재귀 호출로 넘기는 파라미터가 M과 같아지는 시점에 출력시키면 된다.

static void dfs(int index) {
	
    if( index==M ){
    	for(int i=0; i<M; i++) {
        	System.out.print(arr[i] + " ");
        }
        System.out.println();
        return;
    }
    
    	..
}

 

 

전체 코드

---

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

public class Main {
    static int M, N;
    static int[] arr;
    static boolean[] visit;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int index = 1;

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[M];
        visit = new boolean[N + 1];

        recursion(0);
        bw.flush();
        bw.close();
    }

    public static void recursion(int index) throws IOException {
        if (index == M) {
            for (int i = 0; i < M; i++) {
                bw.write(arr[i] + " ");
            }
            bw.write("\n");
            return;
        }

        for (int i = 1; i <= N; i++) {
            if(!visit[i]) {
                arr[index] = i;
                visit[i] = true;
                recursion(index + 1);
                for (int j = i + 1; j <= N; j++) {
                    visit[j] = false;
                }
            }
        }
    }
}