99클럽 코테 스터디 36일차 TIL + 도미노 (DFS)

소개

• 알고리즘 스터디를 참여하며 작성하는 TIL입니다.
• TIL이란? 'Today I Learned'의 약자로, 한국어로 번역하면 '오늘 내가 배운 것'이란 의미입니다.
• 제가 오늘 하루 배운 것 혹은 경험하고 느낀 것들을 기록하고 회고하는 습관을 기르기 위한 글입니다.

 

 

문제 & 키워드

• 백준 - 도미노 (문제 링크)
• 브루트포스
• 백트래킹
• 순열 사이클 분할

 

 

---

 

 

문제 설명

도미노 게임에서 N*N 크기의 보드에 놓인 도미노들 중에서 N개의 도미노를 골라야 합니다. 이때, 선택한 도미노는 같은 행에서 하나, 같은 열에서 하나만 선택할 수 있으며, 선택한 도미노들로 사이클을 만들어야 합니다.

사이클이란 도미노 A의 두 번째 숫자와 도미노 B의 첫 번째 숫자가 같고, 마지막 도미노의 두 번째 숫자가 첫 번째 도미노의 첫 번째 숫자와 같은 경우를 의미합니다.

선택한 도미노들의 뒷면에 쓰인 숫자를 모두 곱한 후, 사이클의 그룹 수가 짝수이면 -1을 곱한 값을 점수로 계산합니다. 주어진 보드에서 얻을 수 있는 최소 점수와 최대 점수를 구하세요.

 

입력

1. 첫째 줄에 N이 주어진다. (N ≤ 6)
2. 다음 N개의 줄에는 각 도미노의 뒷면에 쓰인 숫자가 주어진다.

 

출력

1. 첫째 줄에 최소 점수, 둘째 줄에 최대 점수를 출력한다.

 

입출력 예

 

예제 입력 1

2
35
44

예제 출력 1

-12
20

예제 입력 2

5
00200
0B000
00020
10000
00001

예제 출력 2

-8
0

 

 

---

 

 

문제 접근

1. 문제 이해
   • 주어진 도미노 보드에서 각 행과 열에서 하나씩 도미노를 선택해 사이클을 형성하는 문제입니다.
   • 사이클 그룹의 수가 짝수일 경우 최종 점수에 -1을 곱합니다.
   • 브루트포스와 백트래킹을 이용해 가능한 모든 경우를 탐색하여 최소 및 최대 점수를 구할 수 있습니다.
2. 풀이 방법
   • 백트래킹을 통해 모든 가능한 도미노 조합을 탐색합니다.
   • 각 조합에 대해 사이클을 형성하고, 그 점수를 계산합니다.
   • 모든 조합을 탐색한 후, 최소 점수와 최대 점수를 출력합니다.

 

 

풀이 - Java 코드

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

public class Main {

    private static boolean[] visitedCol;
    private static int minValue = Integer.MAX_VALUE;
    private static int maxValue = Integer.MIN_VALUE;
    private static int n;
    private static int[][] dominoBoard;

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

            n = Integer.parseInt(br.readLine());
            dominoBoard = new int[n][n];
            visitedCol = new boolean[n];

            for (int i = 0; i < n; i++) {

                String line = br.readLine();

                for (int j = 0; j < n; j++) {
                    char dominoValue = line.charAt(j);
                    if ('A' <= dominoValue && dominoValue <= 'I') {
                        dominoBoard[i][j] = '@' - dominoValue; // A는 -1, B는 -2...
                    } else {
                        dominoBoard[i][j] = dominoValue - '0';
                    }
                }
            }

            // 0행에서 시작하는 모든 경우의 수를 구한다.
            for (int i = 0; i < n; i++) {
                dfs(new int[n], 0, i);
            }

            System.out.println(minValue);
            System.out.println(maxValue);

        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    private static void dfs(int[] result, int r, int c) {
        result[r] = c;
        visitedCol[c] = true;

        if (r == n - 1) {
            int score = (countCycle(result) % 2 == 0 ? -1 : 1) * getScore(result);
            minValue = Math.min(minValue, score);
            maxValue = Math.max(maxValue, score);
        } else {
            // 다음 행에서 선택할 도미노 찾기
            for (int i = 0; i < n; i++) {
                if (visitedCol[i]) continue;
                dfs(result, r + 1, i);
            }
        }

        result[r] = 0;
        visitedCol[c] = false;
    }

    private static int countCycle(int[] arr) {
        boolean[] visit = new boolean[n];
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (visit[i]) continue;
            count++;
            int cur = i;
            while (!visit[cur]) {
                visit[cur] = true;
                cur = arr[cur];
            }
        }
        return count;
    }

    private static int getScore(int[] arr) {
        int result = 1;
        for (int i = 0; i < n; i++) {
            result *= dominoBoard[i][arr[i]];
        }
        return result;
    }
}

풀이 설명

1. 초기화
   • 주어진 입력을 통해 도미노 보드를 초기화합니다.
   • 도미노 뒷면의 값이 문자일 경우 이를 숫자 값으로 변환하여 보드에 저장합니다.
2. 백트래킹을 이용한 조합 생성
   • dfs(int[] result, int r, int c) 메서드는 현재 행 r에서 열 c에 해당하는 도미노를 선택합니다.
   • 모든 행에서 하나씩 도미노를 선택하여 사이클을 생성한 후, 해당 사이클의 점수를 계산합니다.
   • 점수를 계산한 후, 최소값과 최대값을 갱신합니다.
3. 사이클의 개수 계산
   • countCycle(int[] arr) 메서드를 통해 주어진 도미노 조합이 몇 개의 사이클을 형성하는지 계산합니다.
   • 사이클의 개수가 짝수일 경우, 점수에 -1을 곱하게 됩니다.
4. 최종 점수 계산
   • getScore(int[] arr) 메서드를 통해 주어진 도미노 조합의 점수를 계산합니다.
   • 계산된 점수는 최종적으로 최소값과 최대값으로 비교되어 결과에 반영됩니다.

 

 

---

 

 

마무리하며

이번 문제는 백트래킹과 브루트포스를 통해 가능한 모든 도미노 조합을 탐색하고, 각 조합에 대해 점수를 계산하는 방식으로 접근했습니다.