💡 문제
권장 시간
- 1시간 30분
소요 시간
- 1시간 30분 + a
나의 풀이 코드
import java.io.*;
public class BOJ1552 {
int[][] map;
int N;
int maxScore = Integer.MIN_VALUE;
int minScore = Integer.MAX_VALUE;
// permutation에서 생성된 순열로 점수 계산
private void calculate(int[] perm) {
boolean[] isVisited = new boolean[N];
int score = 1; // 현재 순열에 대한 점수 (곱하기니까 초기값은 1)
int groups = 0;
for (int i = 0; i < N; i++ ) {
if (!isVisited[i]) {
groups++; // 새로운 그룹 시작
int curr = i;
while (!isVisited[curr]) { // 방문되지 않은 도미노를 따라가며 그룹을 형성
isVisited[curr] = true;
score *= map[curr][perm[curr]]; // 현재 도미노의 값을 점수에 곱함
curr = perm[curr]; // 다음 도미노로 이동
}
}
}
if (groups % 2 == 0) { // 그룹 수가 짝수면
score *= -1; // -1 곱해주기
}
maxScore = Math.max(maxScore, score);
minScore = Math.min(minScore, score);
}
private void swap(int[] perm, int i, int j) {
int tmp = perm[i];
perm[i] = perm[j];
perm[j] = tmp;
}
private void permutation(int[] perm, int idx) {
if (idx == N) { // 현재 인덱스가 N과 같은 경우 (즉, 하나의 순열이 완성된 경우)
calculate(perm);
return;
}
for (int i = idx; i < N; i++) { // idx부터 N까지 순열 생성
swap(perm, idx, i);
permutation(perm, idx + 1); // 다음 인덱스에 대해 순열 생성
swap(perm, idx, i); // 원래 상태로 되돌림 (백트래킹)
}
}
// 메인 로직을 실행하는 함수
public void solution() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map = new int[N][N];
for (int i = 0; i < N; i++) {
String s = br.readLine();
for (int j = 0; j < N; j++) {
char c = s.charAt(j);
if (Character.isLetter(c)) { // 문자인 경우 (A~I)
map[i][j] = -(c - 'A' + 1);
} else { // 숫자인 경우 (0~9)
map[i][j] = Integer.parseInt(String.valueOf(c));
}
}
}
int[] perm = new int[N];
for (int i = 0; i < N; i++) {
perm[i] = i; // 초기 순열을 [0, 1, 2, ..., N-1]로 설정
}
permutation(perm, 0); // 순열 생성 시작 (백트래킹)
System.out.println(minScore);
System.out.println(maxScore);
}
public static void main(String[] args) throws Exception {
new BOJ1552().solution();
}
}
주요사항
이 문제는 주어진 N x N 크기의 보드에서 N개의 도미노를 선택하고, 그 도미노들의 점수를 계산하는 문제입니다. 문제를 해결하기 위해서는 주어진 조건을 만족하는 가능한 모든 도미노 선택 조합을 고려해야 합니다.
문제의 주요 조건:
- 각 행에서 하나씩, 각 열에서 하나씩 도미노를 선택해야 합니다.
- 선택한 도미노들로 사이클을 구성할 수 있어야 합니다. 사이클은 도미노 (i, j)와 (j, k)가 서로 연결되는 방식으로 구성됩니다.
- 사이클 그룹의 수가 짝수라면, 전체 점수에 -1을 곱합니다.
문제 풀이의 개요:
- 입력 처리 및 초기화:
- 주어진 입력으로부터 도미노 보드 값을 처리합니다. 문자가 있을 경우 이를 음수로 변환합니다.
- 순열 생성 및 탐색:
- 각 행에서 하나씩 도미노를 선택하는 모든 가능한 조합(순열)을 생성합니다. 이를 통해 행과 열에서 중복되지 않는 도미노 선택이 가능합니다.
- 사이클 구성 및 점수 계산:
- 각 순열에 대해 도미노의 값들을 곱하여 점수를 계산합니다.
- 선택한 도미노들이 몇 개의 사이클로 구성되는지 확인하고, 사이클의 수가 짝수이면 점수에 -1을 곱합니다.
- 최대 및 최소 점수 추적:
- 모든 가능한 조합에 대해 최대 점수와 최소 점수를 계산합니다.
- 결과 출력:
- 최종적으로 최소 점수와 최대 점수를 출력합니다.
코드의 각 부분에 대한 자세한 설명:
- 입력 처리:
- map[i][j] 배열에 도미노의 값을 저장합니다. 숫자는 그대로, 문자는 음수로 변환합니다.
- 순열 생성:
- 행마다 도미노를 선택하는 모든 가능한 조합을 순열로 생성합니다. 예를 들어, perm = [0, 1, 2]는 첫 번째 행에서 첫 번째 도미노를, 두 번째 행에서 두 번째 도미노를, 세 번째 행에서 세 번째 도미노를 선택하는 경우를 나타냅니다.
- 사이클 구성:
- 선택된 순열에 대해 각 도미노를 방문하면서 사이클을 확인합니다. 한 번 방문한 도미노를 다시 방문하지 않도록 체크하여 그룹을 나눕니다. 각 사이클 그룹의 수를 세어 점수를 계산합니다.
- 백트래킹:
- 순열을 생성할 때, swap을 사용하여 요소들의 위치를 바꾸면서 새로운 조합을 탐색합니다. 각 조합이 끝나면 원래 상태로 되돌려 다음 조합을 탐색할 수 있도록 합니다.
- 최대 및 최소 점수 계산:
- 각 순열에서 계산된 점수를 최대/최소 점수와 비교하여 갱신합니다.
순열 생성과 백트래킹의 구체적인 동작:
- 순열 생성의 시작: idx = 0에서 시작하여, 가능한 모든 조합을 만들기 위해 현재 위치를 다른 위치와 swap합니다.
- 순열을 구성하고 재귀적으로 탐색: 현재 idx에서 선택된 요소를 고정한 후, idx + 1에서 다시 새로운 조합을 만듭니다.
- 백트래킹을 통해 원래 상태로 복원: 재귀 호출이 끝나면, swap을 다시 호출하여 원래 상태로 배열을 복원합니다. 이를 통해 다른 조합을 탐색할 수 있습니다.
예시를 통한 설명:
예를 들어, N = 3이고 보드가 다음과 같이 주어졌다고 가정해봅시다:
2 1 3
4 5 6
7 8 9
이 경우 가능한 순열은 [0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0] 등이 있습니다.
각 순열에 대해 사이클을 구성하고 점수를 계산합니다. 예를 들어, [0, 1, 2]의 경우:
- (1, 1), (2, 2), (3, 3)를 선택
- 사이클 (1, 1) -> (1, 2) -> (2, 3) -> (3, 1)을 구성
- 점수는 2 * 5 * 9 = 90이 되며, 사이클 그룹이 하나이므로 점수를 그대로 유지