백준 - 빌런 호석 22251

백준에서 "빌런 호석" 문제의 풀이를 담고 있습니다.

 

백준 - 빌런 호석 22251

 

 

블로그 목차

 

1. 원리

2. 코드

추천글

 

 

원리

 

- 가장 단순한 방법으로는 모든 칸을 반전시키면서 체크를 하는 것인데 반전을 시켰지만 숫자가 만들어지지 않는 경우가 있을 것이기 때문에 불필요한 탐색을 많이 해야 한다.

- 따라서, 나는 미리 숫자 i와 숫자 j 사이에 몇 개의 칸이 반전되어야 하는지를 행렬에 계산해 두었다.

- 이 행렬이 matrix[][] 일 때, matrix[i][j]는 i에서 j로 바뀌기 위해서는 몇 개의 칸이 반전되어야 하는지를 의미한다.

- 또, j에서 i로 만드는 것과 i에서 j로 만드는 것은 필요 반전 횟수가 같기 때문에 matrix 행렬은 대각선을 기준으로 대칭이 된다.

- 마지막으로 i에서 i로 만드는 것은 0개의 반전이 필요하므로, matrix의 대각성분은 모두 0이다.

 

- 그러면 꺼져있는 칸은 0, 켜져있는 칸은 1로 표시하고 각 칸이 아래 그림과 같이 배열의 index가 될 때 0~9까지의 숫자들을 표시하면 다음과 같다.

디지털 숫자에서 각 칸과 대응되는 배열의index

number = new int[][] {
    {1, 1, 1, 0, 1, 1, 1},
    {0, 0, 1, 0, 0, 1, 0},
    {1, 0, 1, 1, 1, 0, 1},
    {1, 0, 1, 1, 0, 1, 1},
    {0, 1, 1, 1, 0, 1, 0},
    {1, 1, 0, 1, 0, 1, 1},
    {1, 1, 0, 1, 1, 1, 1},
    {1, 0, 1, 0, 0, 1, 0},
    {1, 1, 1, 1, 1, 1, 1},
    {1, 1, 1, 1, 0, 1, 1}
};

 

- 이제 matrix[i][j]를 완성시키면 된다.

- 이것은 number[i]와 number[j]를 비교해서 몇 개의 칸이 다른지를 세면 되는 아주 단순한 문제다.

- matrix 행렬이 완성되면 이제 DFS를 돌린다.

- 각 자릿수에서 특정 숫자로 변경을 한다고 가정하고 해당 숫자로 변경하기 위해서 몇 개의 칸이 반전되었는지를 다음 탐색에 전달하면 된다.

 

- 예를 들어, 문제 예제와 같이 9 1 2 5 가 입력으로 들어왔을 때 matrix[5]의 행을 보면 5에서 2번의 변경을 허용할 때, 어떤 숫자들을 만들어 낼 수 있는지 알 수 있다.

- matrix[5] = [3, 5, 4, 2, 3, 0, 1, 4, 2, 1]

 

- 최초에 DFS에는 반전 횟수 0 (아래 코드에서 rCnt)과 자릿수 0 (아래 코드에서 depth)이 주어진다.

- 예제는 자릿수가 하나이므로 5를 변경하면 바로 0 + 1 = 1이 되어 더 이상의 변경을 허용하지 않는다.

- 자, 그러면 5에서 0으로 변경을 해보자 rCnt는 0 + 3이 된다. 이때, rCnt > P (2) 보다 크기 때문에 이 변경은 허용되지 않는다.

- 5에서 1로 변경을 해보자 rCnt는 0 + 5로 P (2) 보다 크기 때문에 마찬가지로 안된다.

- 이런 식으로 변경이 가능한 숫자를 찾으면 3, 5, 6, 8, 9 가 나온다.

- 그런데 정답은 5개가 아니라 4개이다. 왜냐면 5는 변경을 하나도 안한 것이기 때문이다. 조건에는 나와있지 않지만 이 경우는 암묵적으로 제외시킨다.

- 그래서 아래 코드를 보면 DFS에 target이라는 인자가 존재하는데 제일 처음 입력받은 X를 의미한다.

- 변경을 다 탐색했는데 변경 완료된 숫자가 X와 같으면 해당 경우는 변경으로 치지 않기 위해서이다.

 

- 이 문제를 풀기 위해 꼭 알아야 하는 조건은 아래와 같다.

- 먼저, 자릿수 K는 2인데 X는 5로 한 자릿수가 입력된 경우이다.

- 실제로는 05 라는 식으로 표시되고 있기 때문에 자릿수를 채운 문자열에서 변경을 가해야 한다.

- 즉, "05" 라는 문자열에서 각 자릿수들을 변경해야 한다.

- 두 번째로는 만든 숫자는 0보다 커야한다.

- 나는 이 조건을 놓쳐서 몇 번의 재시도를 거쳤다.

- 마지막으로는 앞에서도 얘기했지만 변경이 완료된 수가 현재 입력받은 수 X와 같으면 안된다.

 

- 혹시 계속 재시도로 고통받고 있다면, 위의 조건들을 잘 살펴보도록 하자.

코드

 

import java.io.*;
import java.util.*;
import java.math.*;
public class Main {
    int N;
    int K;
    int P;
    int X;
    int answer;
    int[][] matrix;
    int[][] number;
    public void input() throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        P = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());
    }

    public int compare(int[] array1, int[] array2) {
        int cnt = 0;
        for (int i = 0; i < array1.length; i++) {
            if (array1[i] != array2[i])
                cnt++;
        }
        return cnt;
    }
    public void makeMatrix() {
        matrix = new int[10][10];

        number = new int[][] {
                {1, 1, 1, 0, 1, 1, 1},
                {0, 0, 1, 0, 0, 1, 0},
                {1, 0, 1, 1, 1, 0, 1},
                {1, 0, 1, 1, 0, 1, 1},
                {0, 1, 1, 1, 0, 1, 0},
                {1, 1, 0, 1, 0, 1, 1},
                {1, 1, 0, 1, 1, 1, 1},
                {1, 0, 1, 0, 0, 1, 0},
                {1, 1, 1, 1, 1, 1, 1},
                {1, 1, 1, 1, 0, 1, 1}
        };
        for (int i = 0; i < 10; i++)
            Arrays.fill(matrix[i], -1);
        for (int i = 0; i < 10; i++) {
            matrix[i][i] = 0;
            for (int j = i+1; j < 10; j++) {
                int diff = compare(number[i], number[j]);
                matrix[i][j] = diff;
                matrix[j][i] = diff;
            }
        }
    }

    public void dfs(int depth, int rCnt, String target, String str) {
        if (depth == K && rCnt <= P) {
            // 이건 만들 수 있는 수
            if (!target.equals(str) && Integer.parseInt(str) <= N && Integer.parseInt(str) > 0) {
                answer++;
            }
        } else if (depth == K) {
            return;
        } else {
            int currNum = Integer.parseInt(target.substring(depth, depth+1));
            for (int i = 0; i < 10; i++) {
                if (matrix[currNum][i] != -1) {
                    dfs(depth + 1, rCnt + matrix[currNum][i], target, str + i);
                }

            }
        }
    }
    public void solution() throws IOException{
        answer = 0;
        makeMatrix();
        // 자릿수 위치, 반전 갯수
        String realX = "";
        if ((""+X).length() < K) {
            int iter = K - ("" + X).length();
            for (int i = 0; i < iter; i++) {
                realX += "0";
            }
            realX += X;
        } else {
            realX = "" + X;
        }
        dfs(0, 0, realX, "");
        System.out.println(answer);
    }
    public void solve() throws IOException{
        input();
        solution();
    }

    public static void main(String[] args) throws IOException {
        new Main().solve();
    }
}

 

오랜만에 풀었던 문제 중에서 가장 재밌게 풀었던 것 같다.

추천글

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