[백준 1311] 할 일 정하기 1 - JAVA

문제 링크

코테 스터디에서 풀었던 내용입니다.
스터디 할 때는 PPT를 열심히 작성해서 발표했기 떄문에
스터디 때 풀었던 문제들에 대해서는 그림 자료를 사용합니다!

---

문제 정의

문제 조건

• $N$명의 사람이 있고, $N$개의 일이 존재
• 각 사람은 정확히 하나의 일만 수행
• 각 일도 정확히 한 사람만이 담당
• 각 사람이 각 일을 수행할 때 비용이 주어짐

입력

• 사람과 일의 수 : 1≤𝑁≤20
• 다음 줄 부터 2차원 cost 배열
  • 𝒄𝒐𝒔𝒕[𝒊][𝒋]는 i번째 사람이 j번째 일을 할 때의 비용을 의미
  • 1≤𝑐𝑜𝑠𝑡[𝑖][𝑗]≤100

출력

• 모든 사람이 서로 다른 일을 한 번씩만 일을 할 때 총 수행 비용의 최솟값 구하기

---

예시

위 사진을 보면 3명의 사람에게 3개의 일이 존재할 때
각각의 사람에게 서로 다른 일을 배정하는 경우의 수입니다.

총 $N!$개의 경우의 수가 존재하는 것을 확인할 수 있습니다.

---

시간 복잡도

사람과 일의 수는 $N$으로 $1$이상 $20$ 이하의 숫자입니다.

완전 탐색

$N$이 $20$일 때

• $20!=20×19×18×⋯×1=2,432,902,008,176,640,000$
• 약 2경 4천조가지의 경우의 수가 존재합니다. $O(N!)$

그러므로 일반적인 완전 탐색은 수행할 수 없다는 것을 알 수 있습니다.

일반적인 DP도 사용할 수 없습니다.

왜 일반적인 DP는 사용할 수 없을까요?

---

일반적인 DP

전날까지 일을 한 사람들이 맡았던 작업을 할 수 없으므로
이전 사람들이 어떤 일을 했는지를 모두 기록되어 있어야 하는데

일반적인 DP[i][j]의 의미는
i번째 사람이 j번째 일을 했을 때의 최소 비용이라는 의미로 사용되는데
그렇게 되면 이전 사람들이 어떤 일을 했는지를 모두 기록되지 않아 데이터가 오염됩니다.

---

비트마스킹 + DP

$N$의 범위가 20 이하 이므로
총 20개의 비트로 20명의 사람에 대한 상태 관리가 가능하고
이 20개의 비트를 정수로 변환하면 약 100만의 숫자이므로
메모리 초과도 발생하지 않습니다.

그래서 비트마스킹 + DP를 사용해서 문제를 풀어보았습니다.

---

---

접근 방법

1. dp 테이블 선언

행을 작업자의 번호와 순서라고 정의하고
열을 선택된 작업들의 상태라고 정의해서 dp 테이블을 선언했습니다.

열에 대한 정의

좀 더 이해하기 쉽게 풀어 설명하면
k번째 비트가 0이면 아직 작업이 수행되지 않은 상태
k번째 비트가 1이면 이미 작업이 수행된 상태
라고 보시면 됩니다.

이 상태를 체킹해서 0인 경우 다음 작업자에게 k번째 일을 넘겨주는 것입니다.

2. 점화식 세우기

저는 현재 상태에서 다음 상태로 확산하는 bottom-up 방식을 사용하겠습니다.

그러면 현재 위치가 dp[i][j]이라고 할 때
다음 작업자인 i+1번 작업자가 알아야할 것은

• i번째 작업자까지 일을 수행한 상태 j일 때
• 맡을 수 있는 다음 작업 k를 찾기
• 이 상태에서 최솟값 갱신

이것을 점화식으로 한다면 아래와 같습니다.

조건

• 현재 비트마스크에 $j$에 $k$번째 일이 포함되어 있지 않을 경우
  • $k \notin j$
• 이전 단계의 상태가 유효할 때
  • $dp[i-1][j] \neq \infty$

점화식

• 현재 상태 도달 시 최솟값 갱신
  • $dp[i][j \cup \{k\}] = \min(dp[i][j \cup \{k\}], dp[i-1][j] + cost[i][k])$

---

예시

이제 점화식도 세웠으니 코드로 구현만 하면 문제를 해결할 수 있습니다.

좀 더 이해하기 쉽도록 예시를 들어드리겠습니다.

---

첫 작업자인 경우 별도의 로직 없이 처음 접근한 경우 최솟값이므로
각각 최솟값을 할당합니다.

---

첫 번째 작업자가 첫 번째 작업을 한 상태인 001에 접근합니다.
이 때 두 번째 작업자는 첫 번째 작업을 제외한 두 번째 세 번째 작업을 수행할 수 있고
그 때의 상태는 101 011 입니다.

각각의 상태에 001 값인 2에
두 번째 작업자가 k번째 일을 했을 때의 비용을 더해
해당 dp 테이블(dp[i][j|(1<<k)])에 최솟값인지 확인하고 갱신합니다.

---

다음은 첫 번째 작업자가 두 번째 작업을 한 상태인 010에 접근합니다.
이 때 두 번째 작업자는 두 번째 작업을 제외한 첫 번째 세 번째 작업을 수행할 수 있고
그 때의 상태는 011 110 입니다.

각각의 상태에 010 값인 3에
두 번째 작업자가 k번째 일을 했을 때의 비용을 더해
해당 dp 테이블(dp[i][j|(1<<k)])에 최솟값인지 확인하고 갱신합니다.

---

다음은 첫 번째 작업자가 세 번째 작업을 한 상태인 100에 접근합니다.
이 때 두 번째 작업자는 세 번째 작업을 제외한 첫 번째 두 번째 작업을 수행할 수 있고
그 때의 상태는 101 110 입니다.

각각의 상태에 100 값인 3에
두 번째 작업자가 k번째 일을 했을 때의 비용을 더해
해당 dp 테이블(dp[i][j|(1<<k)])에 최솟값인지 확인하고 갱신합니다.

---

첫 번째 줄을 채워봤으니 다음 줄은 간략하게 설명하겠습니다.

---

011의 값에 접근합니다.
세 번째 작업을 하지 않은 상태이므로
세 번째 작업을 마친 상태값에 최솟값을 갱신합니다.

---

101의 값에 접근합니다.
두 번째 작업을 하지 않은 상태이므로
두 번째 작업을 마친 상태값에 최솟값을 갱신합니다.

---

110의 값에 접근합니다.
첫 번째 작업을 하지 않은 상태이므로
첫 번째 작업을 마친 상태값에 최솟값을 갱신합니다.

모든 작업이 끝난 후의 상태 dp[N][(1<<N)-1] 값을 출력합니다.

---

간단한 최적화

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static StringTokenizer st;
    static int INF = 200001;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] cost = new int[N][N];
        int[][] dp = new int[N][1 << N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            Arrays.fill(dp[i], INF);
            for (int j = 0; j < N; j++) {
                cost[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int k = 0; k < N; k++) {
            dp[0][1 << k] = cost[0][k];
        }

        for (int i = 1; i < N; i++) {
            for (int j = 0; j < (1 << N); j++) {
                if (dp[i-1][j] == INF) continue;
                for (int k = 0; k < N; k++) {
                    if ((j & (1 << k)) != 0) continue;
                    dp[i][j|(1<<k)] = Math.min(dp[i][j|(1<<k)], dp[i-1][j] + cost[i][k]);
                }
            }
        }
        System.out.println(dp[N-1][(1<<N)-1]);
    }
}