백준 15649 M 과 N (1) Java 풀이

문제

문제 링크: https://www.acmicpc.net/problem/15649

 

백준 알고리즘 단계별로 풀어보기를 하는 중이다.

DP 및 백트래킹에서 다소 약한 모습을 보이는 중이므로 이러한 문제들 위주로 풀이를 기록하고자 한다.

 

접근

문제를 다 풀고 다른 사람들의 풀이를 보니 깊이우선탐색을 통해 이 문제를 많이 푸는 것 같다.

깊이 우선 탐색 (DFS)

(1) 백트래킹의 일종으로

(2) '각 node 를 순회할때 하나의 node 에 도달하면 간선을 통해 인접 노드를 계속 파고들고, 끝까지 간 뒤에 다시 첫 노드로 돌아와 같은 레벨의 노드로 옮겨가는 탐색 방법이다.' 

(3) 넓이 우선 탐색 (BFS) 과 자주 함께 소개된다.

 

말로하면 잘 이해가 안되지만 그림으로 보면 이해가 잘되더라

출처: https://celerdata.com/glossary/breadth-first-search-bfs

 

 

 

이 문제에서는 인접 숫자가 다음 노드로 취급된다.

그리고 해당 숫자 수열 포함 여부를 채크하면서 재귀적으로 dfs 를 호출하므로 부르트포스가 아니라 백트래킹에 해당 된다.

 

풀이

15649 M 과 N (1) 번 문제는 '1 부터 N 까지의 정수 수열을 이용해 길이가 M 인 수열을 만들어 오름차순으로 출력하시오' 라는 문제로 줄일 수 있다.  N 과 M 의 범위가 (1 ≤ M ≤ N ≤ 8) 이므로 큰 부담없이 풀어볼 수 있겠다.

 

나는 보통 하나의 case 를 상정하고 그에 맞춘 나이브한 풀이를 하는 것으로 문제에 대한 감을 익힌다. 그래서 풀이 방법이 step1(), step2(), step3() 로 나뉘어 있고, 정답은 step3() 이다.

 

각각의 step에 대해서 공통적으로 다음의 Main 클래스 안에서 동작한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    // 1 부터 N 까지의 정수 수열을 이용해 길이가 M 인 수열을 만들어 오름차순으로 출력하시오
    static int N;
    static int M;
    static int[] A;
    static boolean[] meet;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        // 만들어져야 하는 수열의 수는 nPm 이다. 'n!/(n-m)!' 경우의 수와 출력값의 수를 대조하여 검산한다.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String [] input = br.readLine().split(" ");

        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        A = new int[M];
        meet = new boolean[N+1];

        // step1(), step2(), step(3) 메서드 호출
        System.out.println(sb);

    }

}

 

3 2 이 인풋으로 들어온 경우에는 step1() 을 통해 풀 수 있겠지만, 이러한 루프를 M 개 만큼 손수 만들어야 하므로 다른 케이스로의 이식성이 낫다.

private static void step1() {
	// N = 3, M = 2 인 경우를 상정
    // 1~3 까지의 수열중에서 2개씩 짝짓는 경우는 이렇게 할 수 있겠지, 그런데 이 루프를 M 개 만들꺼야?
    // 이러한 루프 M개를 컴퓨터가 만들게 해야지?
    for (int i = 1; i < N+1; i++) {
        for (int j = 1; j < N+1; j++) {
            if (i != j) {
                sb.append(i).append(" ").append(j).append("\n");
            }
        }
    }
}

 

 

그 다음 시도는 더 이식성 높은 케이스를 만들기 위해서는 특정 숫자를 만났다는 플래그를 세우고, 앞뒤로 왔다갔다 해야하지 않을까? 하는 생각으로 만들어봤다.

private static void step2() {
    // i 가 j 를 만났다는 플래그 (meet) 를 세워야한다. 이러한 플래그는 i 의 순서일때 계속 유효하다.
    // 하지만 이 방법 역시 루프를 M 개 만들어야 한다는 문제가 있다.
    // 만났다는 플래그(meet)를 적절히 초기화하고 재귀적으로 호출할 수 있는 방법이 필요하다.
    for (int i = 1; i < N+1; i++) {
        boolean[] meet = new boolean[N+1];
        meet[i] = true;
        A[0] = i;
        int aIndex = 1;

        for (int j = 1; j < N+1; j++) {

            if (!meet[j]) {
                A[aIndex] = j;
                aIndex++;
            }

            if (aIndex == M) {
                for (int a : A) {
                    sb.append(a).append(" ");
                }
                sb.append("\n");
                aIndex = 1; // 0번째 인덱스는 이미 i 가 차지하고 있다.
            }

        }
    }
}

여기까지 해보니 플래그를 초기화하고, 수열 A 의 너비를 판단하는 재귀적인 함수가 필요하겠다는 감이 잡히더라

 

그래서 step3 를 만들 수 있었고 정답이었다.

private static void step3(int sequence) {
    // 몇번째 sequence 를 1씩 증가시키면 재귀적으로 호출한다. 이 sequence 는 결국 A 에 숫자가 채우진 개수가 된다.
    if (sequence == M) {
        for (int a : A) {
            sb.append(a).append(" ");
        }
        sb.append("\n");
        return;
    }

    for (int i = 1; i < N+1; i++) {
        if(!meet[i]) {
            meet[i] = true;
            A[sequence] = i;
            step3(sequence+1);
            meet[i] = false; // 재귀가 빠져나왔다면 이 숫자를 만났다는 flag 를 지운다.
        }
    }
}