승봉's 블로그

[JAVA] 조합(Combination)

부르트포스 유형의 알고리즘을 풀다보면 n개 중에 r개를 뽑아 일일이 함수를 실행해서 결과값을 찾는 문제가 자주 나온다. 이때 조합 함수를 정의하여 사용하며, 기본 형식은 아래와 같다.

void combination(int arr[], int index, int n, int c, int target);

위 함수는 조합의 아래의 기본 공식을 이용한다.

​ = ​ + ​

예를 들어 ​ 인 경우, (1,2) (1,3) (1,4) / (2,3) (2,4) (3,4) 의 경우가 존재하는데

1을 선택하는 경우와 1을 선택하지 않은 경우로 나눌 수 있다.

• 1을 선택하는 앞의 경우에는 1을 이미 선택했으므로, 나머지 3개 중 1개를 고르는 ​ 이 남은 것이고,

• 1을 선택하지 않은 경우는 1을 선택하지 않았았으므로, 나머지 중에 2개를 고르는 ​가 남는 것이다.

즉, ​ = ​ + ​ 가 된다.

위 공식을 이용해 조합의 개수를 구하는 함수는 아래와 같다.

int combi(int n, int r){
  if(r==0 || r==n)
      return 1;
   else
       return combi(n-1, r-1) + combi(n-1, r);
}

조합의 개수를 구하는 것이라 경우의 수 각각을 구하는 함수는 아래와 같다.

java

    static void combi(int[] arr, int index, int n, int r, int target) {
        if(r==0) {
            for(int i=0; i<arr.length; i++)
                System.out.print(arr[i] + " ");
            System.out.println();
        }else if(target == n) {
            return;
        }else {
            arr[index] = target;
            combi(arr, index+1, n, r-1, target+1);
            combi(arr, index, n, r, target+1);
        }
    }

arr[] 은 조합으로 고른 원소가 들어가 있는 배열이다. 배열의 크기는 r과 동일해야 한다.

• 예를 들어 ​의 경우는 arr[] 이 {1, 2}, {1, 3} , ... , {3, 4} 의 원소를 갖고 있을 때 if(r==0) 부분이 실행된다. 해당 조합을 가지고 어떤 기능을 수행할 때에는 arr을 인자로 보내는 함수를 여기서 수행하면 된다.

• int n, int r 은 ​ 의 n, r이 들어가면 된다.

• index는 구한 원소의 개수를 의미한다. 즉, 위처럼 해당 원소를 선택한 경우는 하나의 원소가 선택되었으므로 idnex+1로 인자를 보내주고, r-1개를 뽑으면 되므로 , r-1을 인자로 보내준다. 해당원소를 선택하지 않은 경우는 Index가 그대로 유지되며, r도 그대로 유지된다. (이때는 target만 1 증가한다.)

• target은 몇부터 원소를 선택할지를 의미한다. 예를 들어 ​의 경우를 예로 들 때 target = 1은 (1,2) (1,3) (1,4) 를 말하며, target=2일 경우에는 (2,3) (2,4) .. 를 말한다. index의 원소를 선택하거나 안하거나를 결정했으므로, target을 1 증가시켜준다.

• 
  

combination 함수에서는 (0,1,2) (2,3,4).. 등과 같이 자연수 n의 조합을 출력하므로, 2차원 배열의 좌표와 같은 경우에는 (x,y)를 갖는 객체 리스트를 만들어 놓은 다음 combination 함수를 이용해 자연수 조합을 배열 arr로 받은 다음 이 배열을 리스트에 접근하는 원소로 사용할 수 있다.

소스코드 :

ArrayList<Pos> virus_list = new ArrayList();
for(int i=1; i<=N; i++)
    for(int j=1; j<=M; j++)
        if(map[i][j] == 2) {// 바이러스일 경우 바이러스리스트에 넣기 
            virus_list.add(new Pos(i, j));
            
/*....*/
//virus_list 중 3개를 선택하는 경우
combination(new int[3], 0, virus_list.size(), 3, 0);
    

static void combination(int arr[], int index, int n, int r, int target) {
        if(r == 0) {
            // 좌표 조합 (x,y) 출력
            for(int i=0; i<arr.length; i++) 
                System.out.print("(" + virus_list.get(arr[0]).x + "," 
                                 +  virus_list.get(arr[0]).y + ")");
            System.out.println();
        }else if(target == n) {
            return;
        }else {
            arr[index] = target;
            combination(arr, index+1, n, r-1, target+1 );
            combination(arr, index, n, r, target+1);
        }
    }

백준16234 : 인구 이동

문제

2차원 배열에 국가별 인구 수가 주어져있을 때 인접한 국가의 인구수가 주어진 범위 내에 있으면 국경을 열어 인구이동을 하여 1/N인구로 만드는 작업을 반복할 때, 인구이동이 몇 번 일어나는 지 알아내는 문제

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

접근방법

• BFS를 이용해 인접한 영역을 확인하고 인구이동을 한다.

• 인구이동을 한 국가는 booelan moved[][] 를 이용해 표시한다.

• 한 번 전체 국가가 인구이동을 한 뒤에는 이동 수를 증가시키고 moved[][]를 초기화 해준다.

1. BFS를 이용해 인접한 영역 확인하기

• 2개의 boolean 2차원 배열을 사용해주었다.

  1) BFS 체크용 boolean 배열 check[][] 시간이 초과되지 않도록 이미 방문한 배열 체크

  2) 인구이동한 국가 확인용 boolean 배열 moved[][]

• 인접한 배열을 큐에 넣을지 결정하기 위해서는 다음의 네가지를 확인해주어야 한다.

  1) 배열의 범위를 벗어났는가

  • 이 경우는 애초에 배열을 2칸씩 크게 만들어서, 해당 원소의 값이 0인지 여부만 확인해주면 된다.

  2) 아직 인구이동이 되지 않은 지역인가

  • moved 배열 확인

  3) BFS가 이미 방문한 원소인가

  • check 배열 확인

  4) 인구차이가 범위 내에 있는가

• 위 네가지를 확인한 뒤에 큐에 넣어준다.

인구이동이 일어난 국가들의 인구 수를 변경해주기 위해, 큐에서 빼낸 좌표들은 다시 새로운 큐(queue_tmp)에 넣어준다.

• 해당 큐를 이용하여 인구 수를 설정해주고, moved를 함께 체크한다.

• 인접값을 확인하기 전부터 미리 하나는 큐에 들어가므로, 큐의 개수가 1개 초과일 경우가 인구이동이 일어난 경우이다.

소스코드

import java.util.*;
import java.io.*;
​
public class Main{
​
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
​
    static int N;
    static int minGap;
    static int maxGap;
    static int[][] map;
    static boolean[][] moved;
    static boolean isQuit;
​
    static class Pos{
        int x; int y;
        public Pos(int x, int y) {this.x= x; this.y = y;}
    }
​
    static void BFS(int x, int y){
        boolean check[][] = new boolean[N+2][N+2];
        Queue<Pos> queue = new LinkedList();
        Queue<Pos> queue_tmp = new LinkedList();
        queue.offer(new Pos(x, y));
​
        int sum = 0;
        while(!queue.isEmpty()) {
            Pos cur_pos = queue.poll();
            check[cur_pos.x][cur_pos.y] = true;
            sum += map[cur_pos.x][cur_pos.y];
            queue_tmp.offer(new Pos(cur_pos.x, cur_pos.y));
​
            for (int i = 0; i < 4; i++) {
                Pos next_pos = new Pos(cur_pos.x + dx[i], cur_pos.y + dy[i]);
                int gap = Math.abs(map[cur_pos.x][cur_pos.y] - map[next_pos.x][next_pos.y]);
                if( map[next_pos.x][next_pos.y] != 0        // 경계가 아니면서
                        && !moved[next_pos.x][next_pos.y]   // 아직 인구이동이 되지 않은 지역이면서
                        && !check[next_pos.x][next_pos.y]   // <<BFS방문체크>>
                        && gap >= minGap && gap <= maxGap){ // 인구 차이가 범위 내인 경우
                    queue.offer(next_pos);                  // 큐에 넣어준다.
                    check[next_pos.x][next_pos.y] = true;
                }
            }
        }
​
        // 인구이동이 일어난 경우
        if(queue_tmp.size() != 1){
            isQuit = false;
            int value = sum / queue_tmp.size();
            while(!queue_tmp.isEmpty()){
                Pos pos = queue_tmp.poll();
                map[pos.x][pos.y] = value;
                moved[pos.x][pos.y] = true;
            }
        }
​
    }
​
​
    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] input = in.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        minGap = Integer.parseInt(input[1]);
        maxGap = Integer.parseInt(input[2]);
​
        map = new int[N+2][N+2];
        moved = new boolean[N+2][N+2];
        for(int i=1; i<=N; i++){
            String line[] = in.readLine().split(" ");
            for(int j=1; j<=N; j++)
                map[i][j] = Integer.parseInt(line[j-1]);
        }
​
        int result = 0;
        while(true){
            isQuit = true;
            for(int i=1; i<=N ;i++)
                for (int j = 1; j <= N; j++)
                    if (!moved[i][j])
                        BFS(i, j);
​
            if(!isQuit){
                ++result;
                // 인구이동여부 초기화
                for(int i=1; i<=N; i++)
                    for(int j=1; j<=N; j++)
                        moved[i][j] = false;
            } else{ // 인구이동 하나도 없을 시 종료
                break;
            }
        }
​
        System.out.println(result);
    }
}

백준15684 : 사다리 조작

문제

N개의 세로선과 H개의 가로선이 있을 때 i번째 세로선을 타고 다시 i번째로 끝나기 위해 추가해야 될 가로선의 개수를 구하는 문제

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

접근방법

• 3번까지만 사다리를 놓는다는 것을 보고 1번, 2번, 3번 사다리를 일일이 놓아본 다음 다시 본인의 세로선에서 끝나는지를 확인하도록 하였다.

• 기본로직

  // i-i 연결 여부 확인
  if(search(map) == false){ // 초기상태 확인
      ++result;
      isTrue = combi_1(); // 가로선 1개 추가 후 확인
      if(isTrue == false){ 
          ++result;
          isTrue = combi_2(); // 가로선 2개 추가 후 확인
          if(isTrue == false){
              ++result;
              isTrue = combi_3(); // 가로선 3개 추가 후 확인
              if(isTrue == false)
                  result = -1;
          }
      }
  }
  System.out.println(result);

1. i번째 세로선이 사다리를 타고 도달하는 세로선 확인하는 함수 search()

   • 먼저 입력을 받을 때 가로는 N-1개, 세로는 H개의 배열로 받아지는 것을 알 수 있다. 즉, map[i][j] 는 i번째 가로선과 j와 j+1번째 세로선을 잇는 선이 된다.

   • map[H][N-1] 배열에서 i번째 세로선에서 시작해 사다리를 타고 이동할 곳을 알기 위해서는 map[i][j-1] 과 map[i][j] 을 확인해야 한다. 즉, 첫번째경우가 true라면 왼쪽으로 이동하는 것이고, 두번재 경우가 true라면 오른쪽으로 이동하는 경우이다.

   • 여기서 첫번째 세로선과 마지막 세로선은 한방향으로만 이동할 수 있기 때문에 예외처리를 해주어야 한다.

   • map[i][j-1], map[i][j] 에 따라서 세로선 인덱스가 바뀌기 때문에, 마지막에 처음 시작한 인덱스와 비교해주기 위해 n_tmp 를 사용하였다.

   • 소스코드는 아래와 같다.

     // i-i 연결여부 확인
     static boolean search(boolean[][] map){
     ​
         boolean result = true;
         for(int n=1; n<=N; n++){
             int n_tmp = n;
             for(int h=1; h<=H; h++) {
                 // 왼쪽으로 이동 (1은 확인x)
                 if (n > 1 && map[h][n - 1] == true) {
                     --n;
                 }// 오른쪽으로 이동 (N은 확인x)
                 else if (n < N && map[h][n] == true){
                     ++n;
                 }
             }
             if(n != n_tmp){
                 result = false;
                 break;
             }
             n = n_tmp;
         }
     ​
         return result;
     }

2. 가로선을 하나 추가하는 경우는 이차원 배열을 훑으면서 하나씩 가로선을 더해주면 된다.

   • 소스코드

     static void combi_1(){
        boolean map_tmp[][] = new boolean[H+1][N];
         for(int i=1; i<=H; i++)
             for(int j=1; j<=N-1; j++)
                 map_tmp[i][j] = map[i][j];
     ​
         for(int i=0; i<pos_set.length; i++){
             if(pos_set[i] != null){
                 map_tmp[pos_set[i].x][pos_set[i].y] = true;
                 if(search(map_tmp)){
                     isTrue = true;
                     break;
                 }// 바뀐 맵 원래대로 돌려놓기
                 map_tmp[pos_set[i].x][pos_set[i].y] = false;
             }
         }
     }

3. 가로선을 2개, 3개 추가하는 경우는 combination함수를 사용하였다.

• (x, y)의 위치를 조합으로 꺼내야하기 때문에, Pos 객체를 이용해 가로선이 없는 위치를 배열에 넣어주었다.

소스코드

import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;
​
public class Main{
​
    static int N;
    static int M;
    static int H;
    static boolean isTrue;
    static boolean map[][];
    static Pos[] pos_set = new Pos[H*(N-1)];
​
​
    static class Pos{
        int x; int y;
        public Pos(int x, int y) {this.x = x; this.y = y;}
    }
​
    // i-i 연결여부 확인
    static boolean search(boolean[][] map){
​
        boolean result = true;
        for(int n=1; n<=N; n++){
            int n_tmp = n;
            for(int h=1; h<=H; h++) {
                // 왼쪽으로 이동 (1은 확인x)
                if (n > 1 && map[h][n - 1] == true) {
                    --n;
                }// 오른쪽으로 이동 (N은 확인x)
                else if (n < N && map[h][n] == true){
                    ++n;
                }
            }
            if(n != n_tmp){
                result = false;
                break;
            }
            n = n_tmp;
        }
​
        return result;
    }
​
    static void combi_1(){
       boolean map_tmp[][] = new boolean[H+1][N];
        for(int i=1; i<=H; i++)
            for(int j=1; j<=N-1; j++)
                map_tmp[i][j] = map[i][j];
​
        for(int i=0; i<pos_set.length; i++){
            if(pos_set[i] != null){
                map_tmp[pos_set[i].x][pos_set[i].y] = true;
                if(search(map_tmp)){
                    isTrue = true;
                    break;
                }// 바뀐 맵 원래대로 돌려놓기
                map_tmp[pos_set[i].x][pos_set[i].y] = false;
            }
        }
    }
​
    static void combi_2(int arr[]){
        boolean map_tmp[][] = new boolean[H+1][N];
        for(int i=1; i<=H; i++)
            for(int j=1; j<=N-1; j++)
                map_tmp[i][j] = map[i][j];
​
        map_tmp[pos_set[arr[0]].x][pos_set[arr[0]].y] = true;
        map_tmp[pos_set[arr[1]].x][pos_set[arr[1]].y] = true;
​
        if(search(map_tmp))
            isTrue = true;
    }
​
    static void combi_3(int arr[]){
        boolean map_tmp[][] = new boolean[H+1][N];
        for(int i=1; i<=H; i++)
            for(int j=1; j<=N-1; j++)
                map_tmp[i][j] = map[i][j];
​
        map_tmp[pos_set[arr[0]].x][pos_set[arr[0]].y] = true;
        map_tmp[pos_set[arr[1]].x][pos_set[arr[1]].y] = true;
        map_tmp[pos_set[arr[2]].x][pos_set[arr[2]].y] = true;
​
        if(search(map_tmp))
            isTrue = true;
    }
​
    static void combination(int arr[], int index, int n, int r, int target){
        if(arr.length == 1) {
            combi_1();
        }else {
            if (r == 0) {
                if (arr.length == 2) { // 두 개 고르는 경우
                    combi_2(arr);
                } else if (arr.length == 3) { // 세 개 고르는 경우
                    combi_3(arr);
                }
            } else if (target == n) {
                return;
            } else {
                arr[index] = target;
                combination(arr, index + 1, n, r - 1, target + 1);
                combination(arr, index, n, r, target + 1);
            }
        }
    }
​
​
    public static void main(String[] args) throws IOException {
​
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
​
        String input[] = in.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        H = Integer.parseInt(input[2]);
        map= new boolean[H+1][N]; // 한 칸씩 크게 맵을 만들어 줌(H x N-1)
​
        for(int i=0; i<M; i++){
            String line[] = in.readLine().split(" ");
            map[Integer.parseInt(line[0])][Integer.parseInt(line[1])] = true;
        }
​
        isTrue = false;
        int result = 0;
​
        //pos_set = new Pos[H*(N-1)];
        ArrayList<Pos> pos_list = new ArrayList();
        int p_index = 0;
        for(int i=1; i<=H; i++)
            for(int j=1; j<=N-1; j++)
               if(map[i][j] == false)
                   pos_list.add(new Pos(i, j));
        pos_set = pos_list.toArray(new Pos[p_index]);
​
        // i-i 연결 여부 확인
        if(search(map) == false){ // 초기상태 확인
            ++result;
            int arr_1[] = new int[1];
            combination(arr_1,0, pos_set.length, 1, 0);
            if(isTrue == false){ // 가로선 1개 추가 후 확인
                ++result;
                int arr_2[] = new int[2]; // 가로선 2개 추가 후 확인
                combination(arr_2,0, pos_set.length, 2, 0);
                if(isTrue == false){
                    ++result;
                    int arr_3[] = new int[3];
                    combination(arr_3,0, pos_set.length, 3, 0);
                    if(isTrue == false)
                        result = -1;
                }
            }
        }
​
        System.out.println(result);
​
    }
}

- 정답은 맞았지만 시간 상 수정이 필요하다.