문제 이해 단계
https://www.acmicpc.net/problem/21608
자리를 정하는 학생의 번호와 그 학생이 원하는 4명의 학생 번호가 한 줄씩 입력으로 들어온다.
입력 순서가 자리를 정하는 순서이다.
여기서 자리를 정하는 것은 3가지 우선순위가 존재한다.
1. 빈칸 중 자기가 원하는 학생들과 제일 많이 인접한 곳에 위치한다.
2. 1번 조건이 여러 개라면 그중에서 주위에 빈자리가 많은 곳에 위치한다.
3. 1,2번 조건이 여러 개면 작은 행, 작은 열로 자리를 앉는다.
여기서 "인접"이란 말은, 자신의 상하좌우 한 칸에 있으면 인접한 것이다.
이렇게 모두 자리를 앉고, 주위에 자신이 원하는 사람이 얼마나 앉았느냐에 따라 점수를 정한다.
0명 = 0점
1명 = 1점
2명 = 10점
3명 = 100점
4명 = 1000점
이렇게 점수가 정해질 때 총점수의 합을 구하는 것이 문제.
문제 접근 단계
바로 느낌이 온 것은 상하좌우에 인접한 자리가 원하는 학생인지를 탐색하라는 것.
그래프 탐색(BFS)을 쓰라는 것이 바로 느껴졌다.
탐색을 할 때 BFS 형식을 조금 흉내 내서 탐색을 하는 게 편할 것 같다.
그다음으로 주목해서 본 것은 조건의 형식이다.
이 문제에서 조건은 우선순위가 존재한다.
3번 조건이 검사되는 시점에는 이미 1번과 2번 조건은 검사가 완료됐다.
하지만 1번 조건이 검사되는 시점에서는 2번과 3번 조건은 아직 검사가 되지 않는다.
이런 식으로 포함관계가 존재한다.
이를 다르게 말하면 어느 정도 절차적으로 정렬할 수 있다고 할 수 있다.
조건에서 필요한 빈칸의 수, 좋아하는 학생과 앉은 수, 행과 열의 정보를 가지고 있다고 생각해 보자.
그리고 N번 학생이 각 자리에 갔을 때의 그 정보들을 계산해 보자.
예시 케이스로, 다음으로 9번 학생이 들어온다.
9번 학생이 좋아하는 학생 번호는 [8, 1, 2, 3]이다. 빈칸에 들어왔을 때
빈칸과 인접되는 좋아하는 학생 수(매칭)를 적어보면
순서 쌍은 (빈칸의 수, 매칭된 수)로 나타난다.
이제 문제 조건에 따라 생각해 보자. 조건 1에 따라 매칭 수가 제일 많은 (1,1) 두 개 중 하나가 된다.
그럼 (1,1) 2개를 가지고 2번 조건으로 넘어간다.
그리고 빈칸의 개수를 비교해 보면 둘 다 1개이기 때문에 또 3번 조건으로 넘어간다.
3번 조건에 근거하여 행이 더 작은 앞에 있는 (1,1)이 더 작기 때문에 맨 앞에 위치하게 된다.
그다음에 들어오는 수는 8번 학생이고 좋아하는 학생 번호는 [1, 9, 3, 4]이다.
다시 한번 위와 같은 절차를 거쳐 답을 구해보면
1번 조건에 근거해서 매칭된 수가 가장 많은 (1,2)가 8번 학생의 위치가 된다.
이런 로직을 따라 문제를 풀었다.
이를 정렬을 사용하여 설명하면
1. 매칭 수의 내림차순이고,
매칭수가 같다면 빈칸의 개수 순으로 내림차순 정렬한다.
2. 위에 이어서 빈칸의 개수가 같다면
행의 번호순으로 오름차순 정렬한다.
3. 위에 이어서 행의 번호가 같다면
열의 번호순으로 오름차순 정렬한다.
이 규칙에 따라 매칭, 빈칸, 행과 열을 뭉친 정보들을
한 배열의 모아 위의 규칙에 따라 정렬해 준다.
그래서 가장 앞에 있는 것이 최우선순위이기 때문에
해당 행과 열이 해당 학생의 위치가 되는 것이다.
이제 이런 로직에 따라 알고리즘을 구현하면 된다.
문제 구현 단계
정렬 규칙 만들기
// 정보를 모아둔 구조체
struct Info{
int x;
int y;
int empty;
int match;
};
// 정렬 규칙 만들어둔 함수
bool compare(Info a, Info b){
// 매칭 수가 같다면
if(a.match == b.match){
// 빈칸 수가 같다면
if(a.empty == b.empty) {
// 행이 같다면
if(a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
return a.empty > b.empty;
}
return a.match > b.match;
}위에서 언급한 우선순위에 따른 정렬 규칙이다. Info라는 구조체를 선언하여 만들어줬다.
이 안에는 행과 열, 빈칸의 수와 매칭된 수의 정보가 들어있다.
compare에 의해 매칭 수의 내림차순, 빈칸수의 내림차순, 행과 열의 오름차순으로 정렬된다.
학생 자리 탐색 및 자리에 앉히기
int map[21][21]; // 전체 맵 크기
int N; // 입력받은 N
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
// key : 자리에 앉는 학생 번호, x: 행, y: 열
Info bfs(int key, int x, int y){
Info tmp = {x,y,0,0};
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 1 || ny < 1 || nx > N || ny > N) continue;
// 해당 자리가 비어있으면 빈칸+1
if(map[nx][ny] == 0) {
tmp.empty++;
continue;
}
// 해당 자리에 좋아하는 학생이 앉아있다면 매칭+1
for(int j = 0; j < 4; j++){
if(student[key][j] == map[nx][ny]) tmp.match++;
}
}
return tmp; // 갱신된 Info 반환
}
// 해당 학생 자리 선정 프로세스 시작(key : 학생 번호)
void matching(int key){
vector<Info> list; // 해당 칸의 Info 정보를 담음
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
if(map[i][j] == 0) list.push_back(bfs(key,i,j));
}
}
sort(list.begin(),list.end(),compare); // 정렬 규칙에 따라 정렬
map[list[0].x][list[0].y] = key; // 최우선순위 자리에 앉힘
}유사 BFS?라고 해야 하나, 일반적인 BFS랑은 다르게 방문 확인은 안 해도 돼서 구조는 좀 더 단순하다.
여기서 해주는 것은 상하좌우 자리를 다 확인해 주는 것이다.
해당 자리가 0이면 빈칸으로 간주해서 empty+1을 해준다.
0이 아니라 숫자면 누군가 앉아있다는 걸 의미하기 때문에 좋아하는 친구가 앉아있는지를 확인한다.
맞다면 match+1 한다.
그 후 자신의 행과 열 정보, 그리고 empty와 match 정보를 담은 info를 반환한다.
matching은 매개변수로 들어온 학생을 자리에 앉히는 전체적인 프로세스이다.
전체 맵을 확인 해서 빈자리에서만 상하좌우를 확인해서 Info 정보를 얻는다.
그래서 이 값을 모두 벡터 배열 list에 담아
위에 만들어뒀던 정렬 규칙 compare에 따라 정렬 후 최우선순위 자리에 앉힌다.
점수 계산
// 점수 계산
int getScore(){
int sum = 0;
// k : 학생 번호
for(int k = 1; k <= N*N; k++){
for(int i = 1; i <= N; i++){
bool endFlag = false;
for(int j = 1; j <= N; j++){
if(map[i][j] == k){
Info tmp = bfs(k,i,j);
sum += pow(10,tmp.match-1);
endFlag = true;
break;
}
}
if(endFlag) break;
}
}
return sum;
}모두 자리에 앉힌 후, 다시 인접한 자리에 앉은 사람을 조사해서 Info를 갱신한다.
그 후 match 수에 따라 점수를 정하고 sum에 더해준다.
위가 코드에 대한 설명이다.
아래는 전체 코드를 올리고 약간의 설명을 더한 후 끝내겠다.
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
int student[401][4];
int map[21][21]; // 전체 맵 크기
int N; // 입력받은 N
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
// 정보를 모아둔 구조체
struct Info{
int x;
int y;
int empty;
int match;
};
// 정렬 규칙 만들어둔 함수
bool compare(Info a, Info b){
// 매칭 수가 같다면
if(a.match == b.match){
// 빈칸 수가 같다면
if(a.empty == b.empty) {
// 행이 같다면
if(a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
return a.empty > b.empty;
}
return a.match > b.match;
}
// key : 자리에 앉는 학생 번호, x: 행, y: 열
Info bfs(int key, int x, int y){
Info tmp = {x,y,0,0};
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 1 || ny < 1 || nx > N || ny > N) continue;
// 해당 자리가 비어있으면 빈칸+1
if(map[nx][ny] == 0) {
tmp.empty++;
continue;
}
// 해당 자리에 좋아하는 학생이 앉아있다면 매칭+1
for(int j = 0; j < 4; j++){
if(student[key][j] == map[nx][ny]) tmp.match++;
}
}
return tmp; // 갱신된 Info 반환
}
// 해당 학생 자리 선정 프로세스 시작(key : 학생 번호)
void matching(int key){
vector<Info> list; // 해당 칸의 Info 정보를 담음
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
if(map[i][j] == 0) list.push_back(bfs(key,i,j));
}
}
sort(list.begin(),list.end(),compare); // 정렬 규칙에 따라 정렬
map[list[0].x][list[0].y] = key; // 최우선순위 자리에 앉힘
}
// 점수 계산
int getScore(){
int sum = 0;
// k : 학생 번호
for(int k = 1; k <= N*N; k++){
for(int i = 1; i <= N; i++){
bool endFlag = false;
for(int j = 1; j <= N; j++){
if(map[i][j] == k){
Info tmp = bfs(k,i,j);
sum += pow(10,tmp.match-1);
endFlag = true;
break;
}
}
if(endFlag) break;
}
}
return sum;
}
int main(){
scanf("%d",&N);
vector<int> order; // 자리에 앉는 순서
for(int i = 1; i<= N*N; i++){
int key;
scanf("%d",&key);
order.push_back(key);
for(int j = 0; j < 4; j++){
int num;
scanf("%d",&num);
student[key][j] = num;
}
}
// 순서대로 자리에 앉히기 시작
for(int i = 0; i < order.size(); i++){
matching(order[i]);
}
cout << getScore() << "\n";
}
시행착오
처음에는 감이 안 왔었는데, 정렬로 풀 수 있다는 걸 떠올리니까 의외로 금방 풀었다.
구현문제는 풀 때마다 예외처리 때문에 고생했는데 이렇게 푸니까 바로 맞췄다.
오랜만에 깔끔하게 나온 것 같다.
골드 3 풀다가 골드 5 푸니까 체감 난이도가 확 낮아지네