[BOJ/C++] 21608: 상어 초등학교

🏅 Gold 5

✏️ 최종 솔루션

⭐️ 구현

• seq: 자리 배치하는 순서 기록
• board: 해당 자리에 앉는 숫자 기록
• love: love[현재 숫자][선호 숫자]=true 형식으로 선호 관계 저장
• node: {현재 자리 인접 선호 관계 개수, 현재 자리 인접 빈 자리 개수 , 행, 열}

1. 자리 배치하는 순서와 선호 관계 입력 받기
2. 자리 배치하기
   1) 현재 인덱스가 앉을 수 있는 모든 자리를 돌면서 각 자리의 인접 자리 선호관계 개수, 빈 자리 개수 count 해서 node 로 묶어서 우선순위 큐에 저장
   2) 모든 자리 탐색 후에 우선순위 top node 의 행, 열을 현재 인덱스의 자리로 확정하여 board 에 저장
3. 각 자리의 인접 자리 중 선호 관계 개수 count 해서 answer 갱신

📌 self feedback

❗️ vector 정렬 위한 cmp 함수와 큐 정렬 위한 cmp 함수는 방향이 다르다는 것 기억하기
ex) a 기준 오름차순 정렬, b 기준 오름차순 정렬

// struct
struct node {
	int a;
    int b;
}

// vector
bool cmp (node n1, node n2) {
	if(n1.a==n2.a) return n1.b<n2.b;
    return n1.a<n2.a;
}

// queue
struct cmp {
    bool operator()(node n1, node n2) {
        if(n1.a==n2.a) return n1.b>n2.b;
        return n1.a>n2.a;
    }
};

❗️ 완전탐색을 하는 것이 비효율적이라고 생각해서 현재 인덱스와 선호관계에 있는 숫자의 인접 자리부터 탐색하는 방법도 고려했지만 그렇게 되면 여러번 완전탐색을 해야하기 때문에 오히려 더 비효율적
➡️ 완전탐색을 최대한 1번만 할 수 있는 방안을 고민했어야 함
❗️ 모든 조건들을 우선순위 큐로 한번에 정렬하려는 시도는 좋았음
❗️ 선호관계는 단방향 관계이기 때문에 bool 그래프처럼 관리하려는 생각의 전환이 중요했음

✏️ 최종 code

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;

int n;
bool love[401][401]={false};
int board[21][21]={0,};
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

struct node {
    int x;
    int y;
    int lk;
    int emp;
};

struct cmp {
    
    bool operator()(node& n1, node& n2) {
        if(n1.lk==n2.lk) {
            if(n1.emp==n2.emp) {
                if(n1.x==n2.x) return n1.y>n2.y;
                return n1.x>n2.x;
            }
                
            return n1.emp<n2.emp;
        }
        return n1.lk<n2.lk;
    }
    
};

void sit(int cur) {
    priority_queue<node,vector<node>,cmp> pq;
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            
            if(board[i][j]!=0) continue;
            
            int cnt_like=0, cnt_emp=0;
            for(int k=0;k<4;k++) {
                int nx=i+dx[k];
                int ny=j+dy[k];
                
                if(nx<0 || nx>=n || ny<0 || ny>=n) continue;
                
                int next=board[nx][ny];
                
                if(board[nx][ny]==0) cnt_emp++;
                else if(love[cur][next]) cnt_like++;
            }
            
            pq.push({i,j,cnt_like,cnt_emp});
            
        }
    }

    node nd=pq.top();
    board[nd.x][nd.y]=cur;
    
}

int main() {
    
    cin >> n;

    vector<int> seq;
    for(int i=0;i<n*n;i++) {
        int st;
        cin >> st;
        seq.push_back(st);
        
        for(int j=0;j<4;j++) {
            int lk;
            cin >> lk;
            love[st][lk]=true;
        }
    }
    
    for(int i=0;i<seq.size();i++) {
        int cur=seq[i];
        sit(cur);
    }
    
    int ans=0;
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            
            int cur=board[i][j];
            if(cur==0) continue;
            int cnt=0;
            for(int k=0;k<4;k++) {
                int nx=i+dx[k];
                int ny=j+dy[k];
                
                if(nx<0 || nx>=n || ny<0 || ny>=n) continue;
                int next=board[nx][ny];
                
                if(love[cur][next]) cnt++;
            }
            
            ans+=pow(10,cnt-1);
        }
    }
    
    cout << ans;
    
}