99클럽 코테 스터디 36일차 TIL / [백준] 도미노

오늘의 학습 키워드

---

DFS

문제

---

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

• 플랫폼: 백준
• 문제명: 도미노
• 난이도: 골드 5

풀이

---

import java.io.*;
import java.util.*;

public class Main {

    static Map<Character, Integer> numberMap = new HashMap<>();
    static int[] visitedCol;
    static int[][] board;
    static int minAnswer = Integer.MAX_VALUE;
    static int maxAnswer = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        board = new int[n + 1][n + 1];
        visitedCol = new int[n + 1];
        initMap();

        for (int row = 1; row <= n; row++) {
            String str = br.readLine();
            int col = 1;
            for (char c : str.toCharArray()) {
                board[row][col++] = numberMap.get(c);
            }
        }

        for (int col = 1; col <= n; col++) {
            visitedCol = new int[n + 1];
            visitedCol[col] = 1;
            dfs(2, n);
        }

        System.out.println(minAnswer);
        System.out.println(maxAnswer);
    }

    public static void initMap() {
        for (int i = 0; i < 19; i++) {
            if (i > 9) {
                numberMap.put((char) ('A' + (i - 10)), 9 - i);
            } else {
                numberMap.put((char) (i + '0'), i);
            }
        }
    }

    public static void dfs(int row, int n) {
        if (row == n + 1) {
            int sum = 1;

            for (int i = 1; i <= n; i++) {
                sum *= board[visitedCol[i]][i];
            }

            int[] cycle = new int[n + 1];
            int cnt = 0;

            for (int i = 1; i <= n; i++) {
                if (cycle[i] == 0) {
                    calcCycle(cycle, i, i);
                    cnt++;
                }
            }

            if (cnt % 2 == 0) {
                sum *= -1;
            }

            minAnswer = Math.min(minAnswer, sum);
            maxAnswer = Math.max(maxAnswer, sum);

            return;
        }

        for (int nc = 1; nc <= n; nc++) {
            if (visitedCol[nc] == 0) {
                visitedCol[nc] = row;
                dfs(row + 1, n);
                visitedCol[nc] = 0;
            }
        }
    }

    public static void calcCycle(int[] cycle, int prev, int group) {
        int cur = visitedCol[prev];

        if (cycle[prev] != 0) {
            return;
        }

        cycle[prev] = group;
        calcCycle(cycle, cur, group);
    }
}

접근

• 같은 행과 열에 위치한 도미노를 선택할 수 없다는 특징은 N-Queens 문제와 유사합니다.
• 따라서, DFS로 탐색을 진행합니다.
  • depth는 행을 의미하고, for문을 돌면서 가능한 열을 체크하는 완전 탐색 방식입니다.

    public static void dfs(int row, int n) {
        if (row == n + 1) {
            int sum = 1;
    
            for (int i = 1; i <= n; i++) {
                sum *= board[visitedCol[i]][i];
            }
    
            int[] cycle = new int[n + 1];
            int cnt = 0;
    
            for (int i = 1; i <= n; i++) {
                if (cycle[i] == 0) {
                    calcCycle(cycle, i, i);
                    cnt++;
                }
            }
    
            if (cnt % 2 == 0) {
                sum *= -1;
            }
    
            minAnswer = Math.min(minAnswer, sum);
            maxAnswer = Math.max(maxAnswer, sum);
    
            return;
        }
    
        for (int nc = 1; nc <= n; nc++) {
            if (visitedCol[nc] == 0) {
                visitedCol[nc] = row;
                dfs(row + 1, n);
                visitedCol[nc] = 0;
            }
        }
    }

    • visitedCol 배열
      • 인덱스가 열을 의미하고, 배열의 값은 해당 열에 선택된 도미노의 행을 의미합니다.
    • 만약 마지막 행까지 모두 탐색이 되었다면, 선택된 도미노들의 sum을 구하고, 사이클 개수를 구하여 그 개수가 짝수인 경우 -1을 곱해줍니다.

      public static void calcCycle(int[] cycle, int prev, int group) {
          int cur = visitedCol[prev];
      
          if (cycle[prev] != 0) {
              return;
          }
      
          cycle[prev] = group;
          calcCycle(cycle, cur, group);
      }

      • 사이클 여부는 visitedCol 배열을 활용하여 구했습니다.
      • 재귀를 이용하여 사이클을 추적하고, 사이클인 것들은 cycle 배열에 같은 group 숫자 값을 저장하여 구분합니다.

소요 시간

1시간 30분