세준이가 가지고 있는 도미노는 약간 다르다. 세준이는 도미노를 N2개 가지고 있다. 따라서 N=2라면, 세준이는 (1,1), (1,2), (2,1), (2,2) 이렇게 총 N2개를 가지고 있는 것이다.
세준이는 이 도미노를 가지고 도미노미도마도라는 게임을 하려고 한다. 이 게임은 김민오가 만들었다.
이 게임에서 도미노는 N*N크기의 보드에 놓여져 있다. i번째 행, j번째 열에는 (i,j)라고 쓰여 있는 도미노가 놓여져 있다. 플레이어는 도미노를 정확하게 N개를 골라야 하는데, 선택한 도미노를 두 개가 같은 행에서 고르고, 선택한 도미노를 같은 열에서 고르면 안 된다는 조건이 있다. 또, 고른 도미노를 가지고 사이클을 만들 수 있다. 사이클을 만드는 방법은, 도미노 A와 B가 있을 때, A의 두 번째 숫자와 B의 첫 번째 수가 같으면 된다. 그리고 사이클을 이루는 첫 번째 도미노의 처음 숫자와 마지막 도미노의 둘째 숫자가 같으면 된다.
예를 들어, (1,3), (3,2), (2,4), (4,1)을 골라서 사이클을 만들 수 있다.
N개의 도미노를 고르면 이러한 사이클이 한 개 또는 그 이상의 그룹이 나온다. (1,1)와 같은 도미노는 자기 자신으로 사이클을 이루므로 하나의 그룹이다.
게임의 조건 중에 각 행과 열에서 중복되면 안되는 조건이 있기 때문에, 항상 사이클을 이룰 수 있다.
모든 도미노는 그 뒷면에 숫자가 쓰여 있다. 이 게임에서 점수를 계산할 때는 자기가 고른 도미노의 뒷면에 쓰여 있는 수를 모두 곱한다. 그 다음에 만약 사이클 그룹의 개수가 짝수가 되면 그 수에 -1을 곱한다.
세준이는 자기가 이 게임에서 얻을 수 있는 최대 점수와 최소 점수가 궁금해 졌다.
도미노의 개수와 도미노 뒷면에 쓰여 있는 수가 주어질 때, 세준이가 얻을 수 있는 최대 점수와 최소 점수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. N은 6보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 도미노에 쓰여 있는 수가 주어진다. i행 j열에 쓰여 있는 수는 도미노 (i,j)의 뒷 면에 쓰여 있는 수이다. 도미노의 뒷면에는 0부터 9까지의 수와 A부터 I까지 알파벳 대문자가 쓰여 있고, A부터 I까지 문자가 의미하는 것은 -1부터 -9까지이다.
출력
첫째 줄에 세준이가 얻을 수 있는 최소 점수, 둘째 줄에 세준이가 얻을 수 있는 최대 점수를 출력한다.
예제 입력 1복사
2
35
44
예제 출력 1복사
-12
20
예제 입력 2복사
5
00200
0B000
00020
10000
00001
예제 출력 2복사
-8
0
예제 입력 3복사
3
12A
A12
2A1
예제 출력 3복사
-1
8
예제 입력 4복사
4
AAAA
BBBB
CCCC
DDDD
예제 출력 4복사
-24
24
내가 작성한 코드는 아래와 같다.
import java.util.*;
import java.io.*;
public class Main {
static int n;
static int[][] board;
static boolean[] visited;
static ArrayList<Integer> minos;
static int[] answer;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
board = new int[n][n];
// 최소 점수, 최대 점수 값 저장
answer = new int[] {Integer.MAX_VALUE, Integer.MIN_VALUE};
for(int i=0; i<n; i++) {
String input = br.readLine();
for(int j=0; j<n; j++) {
char c = input.charAt(j);
if(Character.isDigit(c)) {
// 0~9
board[i][j] = c - '0';
} else {
// A~I
board[i][j] = -(c - 'A' + 1);
}
}
}
minos = new ArrayList<>();
visited = new boolean[n];
permutate(0);
StringBuilder sb = new StringBuilder();
sb.append(answer[0]).append("\n").append(answer[1]);
System.out.println(sb.toString());
}
// 순열 생성
static void permutate(int depth) {
if(depth == n) {
// 순환 만들어 졌으므로, 점수 계산
calScore();
return;
}
for(int i=0; i<n; i++) {
if(!visited[i]) {
visited[i] = true;
minos.add(i);
permutate(depth+1);
minos.remove(minos.size() - 1);
visited[i] = false;
}
}
}
static void calScore() {
int score = 1;
int cycles = 0;
boolean[] cycleVisited = new boolean[n];
for(int i=0; i<n; i++) {
score *= board[i][minos.get(i)];
}
// 사이클 개수 확인
for(int i=0; i<n; i++) {
if(!cycleVisited[i]) {
cycles++;
int cur = i;
while(!cycleVisited[cur]) {
cycleVisited[cur] = true;
cur = minos.get(cur);
}
}
}
// 짝수라면 -1 곱함
if(cycles % 2 == 0) {
score *= -1;
}
answer[0] = Math.min(answer[0], score);
answer[1] = Math.max(answer[1], score);
}
}
[풀이 과정]
static 변수들부터 먼저 살펴보겠다.
int n : 보드 크기
int[][] board : 보드 뒷면에 숫자를 저장하는 2차원 배열
boolean[] visited : 순열 생성 시 방문 여부를 판단하는 배열
ArrayList<Integer> minos: 현재 순열 저장 (인덱스는 행을 나타내고, 값은 열을 나타낸다. 예를 들어, minos.get[0] = 2라면, 0 번째 행에서 2번째 수열의 값을 나타낸다 => board[0][2])
1. 각 점수를 숫자, 알파벳에 따라 다르게 계산해주고, board 배열에 값을 저장한다.
2. 순열을 만들면서, N 개인 도미노를 만들었을 때 점수를 계산한다. (permutate() 메서드 -> 순열 만드는 메서드, calScore() 메서드 -> 도미노가 N 개가 되었을 때 점수를 계산하는 메서드)
3. calScore() 메서드에서 사이클의 개수를 먼저 계산한다. 이때 하나의 사이클은 도미노들의 연결이 닫힌 고리 형태로 순환되는 것을 말한다. for문을 돌면서 i번째 도미노를 시작점으로 사이클을 형성하는 도미노를 찾는다. for문 내부 while문을 통해, 도미노가 포함된 사이클을 따라가며 모든 도미노를 방문 표시한다. 마지막으로, cur=minos.get(cur);를 통해 현재 도미노에서 다음 도미노로 이동한다.
4. 이를 통해 for문에서 각 순열에 대해 몇 개의 독립된 사이클이 존재하는지를 확인한다. minos 리스트를 따라가며 사이클을 추적하고, 각 사이클에 속하는 모든 도미노를 한 번씩 방문하게 된다.
