문제 소개
n × n 크기의 행렬이 하나 주어진다고 가정해 보겠습니다. 행렬의 모든 원소는 서로 중복되지 않으며, 1부터 n2 사이의 정수 값만을 가집니다. 우리는 다음 두 가지 연산을 원하는 만큼, 그리고 어떤 순서로든 반복해서 수행할 수 있습니다.
행렬에 있는 두 정수 x와 y(단, 1 ≤ x < y ≤ n)를 골라, x가 들어 있는 열과 y가 들어 있는 열을 서로 맞바꿉니다.
행렬에 있는 두 정수 x와 y(단, 1 ≤ x < y ≤ n)를 골라, x가 들어 있는 행과 y가 들어 있는 행을 서로 맞바꿉니다.
이때 유의할 점은 x + y ≤ k 조건을 만족해야 하며, 두 값은 서로 다른 행과 서로 다른 열에 위치해야 한다는 것입니다.
목표는 위 연산들을 통해 만들어 낼 수 있는 고유한(서로 다른) 행렬의 개수를 구하는 것입니다.
예시
입력이 n = 3, k = 15, mat = {{4, 3, 6}, {5, 9, 7}, {1, 2, 8}}이라면 출력은 36이 됩니다.
예를 들어 두 값을 x = 3, y = 5로 선택한 뒤 해당하는 열들을 맞바꾸면 결과 행렬은 다음과 같습니다.
3 4 6
9 5 7
2 1 8
이런 방식으로 만들 수 있는 고유한 행렬은 총 36개입니다.
풀이 접근 방법
이 문제의 핵심은 "서로 교환 가능한 행(열)"들을 하나의 그룹으로 묶고, 각 그룹 안에서 행(열)의 순서를 자유롭게 배치하는 경우의 수를 곱하는 것입니다. 해결 절차는 다음과 같습니다.
dfs(k, ver, visited, s) 함수를 정의합니다.
visited[k]가 참이면:
return
visited[k] := true
k를 스택 s에 삽입
j := ver[k]의 시작부터 마지막 요소까지 1씩 증가시키며 반복:
dfs(*j, ver, visited, s)
크기가 51인 배열 f를 정의합니다.
f[0] := 1
i := 1부터 50까지 1씩 증가시키며 반복:
f[i] := (i * f[i - 1]) mod modval
크기가 n인 배열 e와 pk를 정의합니다.
i := 0부터 n-1까지 반복:
j := i + 1부터 n-1까지 반복:
chk := 0
l := 0부터 n-1까지 반복:
if (mat[i][l] + mat[j][l]) > k라면:
chk := 1
반복문 탈출
chk가 0이라면:
pk[i]의 끝에 j를 삽입
pk[j]의 끝에 i를 삽입
chk := 0
l := 0부터 n-1까지 반복:
if (mat[l][i] + mat[l][j]) > k라면:
chk := 1
반복문 탈출
chk가 0이라면:
e[i]의 끝에 j를 삽입
e[j]의 끝에 i를 삽입
resa := 1, resb := 1
크기가 n인 배열 v1과 v2를 정의합니다.
i := 0부터 n-1까지 반복:
v1[i] := false
v2[i] := false
i := 0부터 n-1까지 반복:
스택 s를 하나 생성
v1[i]가 거짓이라면:
dfs(i, pk, v1, s)
s가 비어 있지 않다면:
resa := resa * (f[s의 크기])
resa := resa mod modval
i := 0부터 n-1까지 반복:
스택 s를 하나 생성
v2[i]가 거짓이라면:
dfs(i, e, v2, s)
s가 비어 있지 않다면:
resb := resb * (f[s의 크기])
resb := resb mod modval
((resa * resb) mod modval) 출력
알고리즘 동작 원리
팩토리얼 배열 f: 모듈러 값(modval = 998244353)으로 나눈 나머지를 미리 계산해 둡니다. 하나의 교환 가능 그룹 안에서 행(또는 열)들의 순서를 배열하는 경우의 수는 그룹 크기의 팩토리얼과 같기 때문입니다.
그래프 배열 pk와 e: 각각 "행끼리 교환 가능 여부", "열끼리 교환 가능 여부"를 나타내는 무방향 그래프의 인접 리스트입니다. 두 행 i, j의 모든 대응 원소 합이 k 이하라면 두 행은 자유롭게 교환할 수 있으므로 간선으로 연결됩니다. 열에 대해서도 동일하게 검사합니다.
DFS 탐색: 그래프를 깊이 우선 탐색하면서 하나의 연결 요소(교환 가능 그룹)에 속한 정점들을 스택에 모읍니다.
최종 답 계산: 행 그래프의 각 연결 요소 크기에 대한 팩토리얼을 모두 곱한 resa와, 열 그래프에 대해 같은 방식으로 구한 resb를 곱한 뒤 모듈러 연산을 적용하면 정답이 됩니다.
C++ 구현 예시
아래 구현 예시를 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
#define modval 998244353
const int INF = 1e9;
void dfs(int k, vector<int> ver[], bool visited[], stack<int> &s) {
if(visited[k])
return;
visited[k] = true;
s.push(k);
for(vector<int> :: iterator j = ver[k].begin(); j!=ver[k].end(); j++)
dfs(*j, ver, visited, s);
}
void solve(int n, int k, vector<vector<int>> mat) {
int f[51];
f[0] = 1;
for(int i = 1; i <= 50; i++) {
f[i] = (i * f[i-1]) % modval;
}
vector<int> e[n];
vector<int> pk[n];
for(int i = 0; i < n; i++) {
for(int j = i + 1;j < n; j++) {
int chk = 0;
for(int l = 0; l < n; l++){
if((mat[i][l] + mat[j][l]) > k) {
chk = 1;
break;
}
}
if(chk==0) {
pk[i].push_back(j);
pk[j].push_back(i);
}
chk = 0;
for(int l = 0;l < n; l++) {
if((mat[l][i] + mat[l][j]) > k){
chk = 1;
break;
}
}
if(chk == 0) {
e[i].push_back(j);
e[j].push_back(i);
}
}
}
int resa = 1, resb = 1;
bool v1[n], v2[n];
for(int i = 0; i < n; i++) {
v1[i] = false;
v2[i] = false;
}
for(int i = 0;i < n; i++) {
stack<int> s;
if(!v1[i]) {
dfs(i, pk, v1, s);
if(!s.empty()) {
resa *= (f[s.size()]) % modval;
resa %= modval;
}
}
}
for(int i = 0 ;i < n; i++) {
stack<int> s;
if(!v2[i]){
dfs(i, e, v2, s);
if(!s.empty()) {
resb *= (f[s.size()]) % modval;
resb %= modval;
}
}
}
cout<< (resa * resb) % modval;
}
int main() {
int n = 3, k = 15;
vector<vector<int>> mat = {{4, 3, 6}, {5, 9, 7}, {1, 2, 8}};
solve(n, k, mat);
return 0;
}
입력
3, 15, {{4, 3, 6}, {5, 9, 7}, {1, 2, 8}}출력
36