[알고리즘 문제해결 전략]6장_소풍 PICNIC 문제

HMS·2023년 3월 27일

알고리즘

알고리즘 문제해결 전략

목록 보기

1/3

문제를 완전탐색으로 해결하기 위한 과정

완전 탐색은 존재하는 모든 답을 하나씩 검사하므로, 검사에 걸리는 시간은 답의 수에 비례한다. 최대 크기의 입력을 가정했을 때 답의 개수를 계산하고 그것을 제한시간 내에 생성할 수 있는지를 가늠해야한다. 제한 시간을 초과할 것 같다면 다른 알고리즘을 사용해 풀어야 한다.
가능한 모든 답의 후보를 만드는 과정을 여러개의 선택으로 나누며 각 선택은 답의 후보를 만드는 과정의 한 조각이 된다.
그중 하나의 조각을 선택해 답의 일부를 만들고 나머지 답을 재귀 호출을 통해 완성한다.
조각이 하나밖에 남지 않은경우 혹은 하나도 남지 않는 경우에는 답을 생성했으므로 이것을 기저 사례로 선택해 처리한다.

완전탐색이 되기위한 조건

입력의 크기가 작은 경우
입력의 크기가 작으면 모든 경우를 탐색해도 실행시간이 적당하게 소요될 수 있습니다. 따라서, 입력의 크기가 작은 경우에는 완전탐색을 사용하는 것이 적절합니다.
최적해가 유일한 경우
최적해가 유일한 경우, 즉 하나의 결과만 존재하는 경우에는 완전탐색을 사용하는 것이 적절합니다.
탐색해야 하는 경우의 수가 적은 경우
모든 경우를 탐색해야 하므로 탐색해야 하는 경우의 수가 많을수록 실행시간이 증가합니다. 따라서, 경우의 수가 적을 경우에는 완전탐색을 사용하는 것이 적절합니다.
부분해가 쉽게 구할 수 있는 경우
모든 경우를 탐색하지 않고도 최적해에 가까운 부분해를 구할 수 있는 경우에는 완전탐색을 사용하지 않아도 됩니다.
가지치기 (Pruning)가 가능한 경우
가지치기를 통해 실행시간을 줄일 수 있는 경우에는 완전탐색을 사용하는 것이 적절합니다.

문제와 부분문제의 정의

문제란 항상 수행해야 할 작업과 그 작업을 적용할 자료의 조합을 의미한다. 이 문제를 해결하기 위해서 여러개의 부분문제로 분할하여 해결해야 한다.
부분문제란 전체적인 문제를 해결하기 위해 분할한 작은 문제를 말한다. 부분 문제들은 전체적인 문제와 유사하며 같은 알고리즘을 적용하여 해결한다.

6.3 문제 : 소풍

https://algospot.com/judge/problem/read/PICNIC

문제

안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어 줘야 합니다.

각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝지어줄 수 있는 방법의 수를 계산하는 프로그램을 작성하세요. 짝이 되는 학생들이 일부만 다르더라도 다른 방법이라고 봅니다. 예를 들어 다음 두 가지 방법은 서로 다른 방법입니다.

(태연,제시카) (써니,티파니) (효연,유리)
(태연,제시카) (써니,유리) (효연,티파니)

입력

입력의 첫 줄에는 테스트 케이스의 수 C (C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 학생의 수 n (2 <= n <= 10) 과 친구 쌍의 수 m (0 <= m <= n*(n-1)/2) 이 주어집니다. 그 다음 줄에 m 개의 정수 쌍으로 서로 친구인 두 학생의 번호가 주어집니다. 번호는 모두 0 부터 n-1 사이의 정수이고, 같은 쌍은 입력에 두 번 주어지지 않습니다. 학생들의 수는 짝수입니다.

출력

각 테스트 케이스마다 한 줄에 모든 학생을 친구끼리만 짝지어줄 수 있는 방법의 수를 출력합니다.

예제 입력

3
2 1
0 1
4 6
0 1 1 2 2 3 3 0 0 2 1 3
6 10
0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5

예제 출력

1
3
4

문제풀이

문제를 보고 도대체 이게 무슨말이지? 하고 한참을 해메었던것 같다.
때문에 문제의 조건들과 입출력되는 값들이 무엇을 뜻하는지부터 한줄한줄 적으며 정리하는 단계를 거쳤다.

1. 문제 해석단계

테스트 케이스의 수 c<50 가 주어지고
학생수 2<=n<=10 과 친구 쌍의 수 m이 입력으로 주어짐
서로 친구인 학생의 관계가 주어짐 학생의 번호가 m*2만큼 주어지는데 [0,1,0,2,2,3] 이런식이면 0,1/0,2/2,3 그룹이 친구관계
2번과 3번 묶음이 하나의 테스트 케이스다.
테스트 케이스 c 만큼 반복하여 친구 명단을 이용하여 짝이 될 수 있는 경우의 수를 구한다.

2. 풀이 고민

각 조건들을 입력받아야하기 때문에 bufferedreader를 생성하여 조건을 입력받는다.
int c에 테스트 케이스를 입력받는다.
테스트 케이스 만큼 반복시켜줄 for문을 작성한다.
n과 m에 각각 학생수와 친구쌍 수 를 입력받는다.
m만큼 반복하는 for문을 작성하여 학생들의 관계를 입력받는다.
5-1. 어떤 형식으로 입력받을것인가? int[][]이중배열로 ex) {(1,2,3),(3,0),(1,3)..} 입력받는 방법을 생각해 보았으나 학생마다 친구의 수가 다른데 배열의 크기를 변경할 수 없기때문에 불가. 2중 ArrayList<ArrayList> 같은 방식도 생각해 보았으나 너무 복잡할것같아 패스
5-2. boolean[][]배열을 사용하면 default값이 false이기 때문에 입력받는 관계들만 true로 설정해주고 for문을 돌리며 true를 제거해주면 될것같음.
boolean[] 배열에 선택된 학생들을 true처리 해 놓으면 false인 경우만 체크할 수 있을것임
인원수만큼 그룹이 완성되었으면 기저사례로 보내서 스택이 해제 되도록 설정하면 될것 같음

3. 풀이 과정에서의 고민

문제에서 주어진 친구 그룹의 경우 규칙이 존재하지 않았다. 때문에 모든 경우의 수를 따져가며 체크를 해야 답을 도출해 낼 수 있는 완전탐색이 될 수 밖에 없었다고 생각한다.
실제 문제를 풀때는 재귀의 과정이 너무 이해가 되지 않아 코드를 작성하고 디버깅하여 입력되는 값과 재귀시에 flag가 제대로 작동을 하고 있는지 확인하며 문제를 풀었다.
flag가 제대로 동작을 하면 재귀이후 check배열에 선택했던 번호는 true처리가 되고 loop문으로 다시 접근했을 때 선택되지 않은 번호와 반복문의 변수가 들어간 friends배열을 차레로 모두 따져가며 true인 값을 찾아가는 과정을 디버깅을 통해 확인할 수 있었다.

4. 작성된 코드

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

public class Picnic {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int c = Integer.parseInt(br.readLine());// 테스트 케이스 수
        // 테스트 케이스의 수 만큼 테스트 케이스 생성
        for(int i = 0; i < c; i++){
            int n = 0; // 학생수
            int m = 0; // 친구 쌍 수
            boolean[][] friends = new boolean[n][n];
            boolean[] check = new boolean[n];

            while(n < 2 || n >10 || m < 0 || m > n*(n-1)/2){
                System.out.print("n 입력 : ");
                n = Integer.parseInt(br.readLine());
                System.out.print("m 입력 : ");
                m = Integer.parseInt(br.readLine());
            }

            for(int j = 0; j < m; j++){
                System.out.println(m);
                System.out.print("first 입력 : ");
                int first = Integer.parseInt(br.readLine());
                System.out.print("second 입력 : ");
                int second = Integer.parseInt(br.readLine());
                friends[first][second] = true;
                friends[second][first] = true;
            }

            System.out.println(picnic(check,friends,n,n/2));
        }
    }
    static int picnic(boolean[] check,boolean[][] friends,int n,int count){
        if(count == 0){ // 기저사례 : 선택한 그룹이 n/2가 된 경우 return ex)학생이 6명일때 3그룹이 생기면 return
            return 1;
        }
        int k = 0; // 시작할 번호 지정
        for(int i = 0; i < n; i++){
            if(check[i] == false){ // 이전에 선택된적 없는 번호 선택
                k=i;
                break;
            }
        }
        int result = 0; // 기저사례에 도착할 때 마다 +1 되어 횟수 카운트
        for(int i = 0; i < n; i++){
            if(check[i] == false && friends[k][i] == true){ // 시작번호가 선택된적없고, 두 번호가 친구리스트에 있는경우
                check[k] = true; // 체크리스트에 선택된 번호 체크
                check[i] = true; // 체크리스트에 선택된 번호 체크
                count--; // 한 그룹이 생길 때 마다 count에서 -1
                result += picnic(check, friends, n, count);
                count++; // 기저사례 도착하면 count +1
                check[i] = false; // 마지막에 생긴 그룹의 선택을 해제 해 줘야 다른 경우의 수를 찾을 수 있음
                check[k] = false;
            }
        }
        return result;

    }


}

알고리즘 문제를 풀면서 보완해야 했던점

단락나누기
좋은 코드를 작성하기 위해서는 가독성이 좋아야 한다. 변수선언부는 변수선언부 끼리 모아주고 루프나 조건처럼 한번에 봐야하는 부분들은 단락을 나눠줘 한번에 어떤 코드인지 알아볼 수 있어야 한다.
변수의 네이밍 신경쓰기
문제에서 주어진 입력값이 c 혹은 n,m 등이라고 해서 변수를 꼭 같은 네이밍을 해야하는것은 아니다. 위 문제같은경우 테스트 케이스 갯수인 c는 T로 학생수는 studentNum등으로 변수가 뜻하는것이 무엇인지 직관적으로 알 수 있게 작성하는것이 좋은 코드이며, 추후 면접이나 코드를 설명해야 하는 자리에서도 쉽게 설명하고 쉽게 상대방을 이해시킬 수 있을것이다.
2-1. 테스트 케이스는 T로 테스트 케이스를 돌리는 for문의 변수는 t로 설정하는것이 관용적인 방법이다.
boolean은 flag라고도 한다. 깃발을 뽑고 회수하는 작업에서 특정 상태를 나타내는 작업을 나타낼 수 있기 때문이다.
dfs탐색에서는 이미 방문한 노드인지 여부를 나타내는 용도로 사용하여 특정 조건이 만족되었는지 확인할 때 사용하기도 한다.
소풍 문제에서는 check라는 불리안 변수를 사용해 그룹화 된 학생의 상태를 나타내는데 사용되었다.

HMS

안녕하세요

다음 포스트

[알고리즘 문제해결 전략]6장_소풍 PICNIC 문제