백준 21680 상어 초등학교 C++

https://www.acmicpc.net/problem/21608

21608번: 상어 초등학교

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ21608.cpp

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

//
//  main.cpp
//  BJ21608_1
//
//  Created by Hwayeon on 2021/10/17.
//

#include <iostream>
#include <math.h>
#include <vector>
#include <queue>
using namespace std;

int N;
int room[21][21] = {0, };

struct Student{
    int s_id;
    int like[4] = {0, };
};
Student st;
Student students[401];
vector<Student> cmds;

struct Seat{
    int x;
    int y;
    int hole = 0;
    int like = 0;
};
Seat seat;
struct cmp{
    bool operator()(Seat s1, Seat s2){
        if(s1.like == s2.like){
            if(s1.hole == s2.hole){
                if(s1.y == s2.y){
                    return s1.x > s2.x;
                }
                return s1.y > s2.y;
            }
            return s1.hole < s2.hole;
        }
        return s1.like < s2.like;
    }
};
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

int satisfy = 0;

void find_seat(Student st){
    priority_queue<Seat, vector<Seat>, cmp> pq;
    for(int y=1; y<=N; y++){
        for(int x=1; x<=N; x++){
            if(room[y][x] > 0) continue;
            Seat new_seat;
            new_seat.x = x;
            new_seat.y = y;
            //1. 인접한 좋아하는 학생 수와 빈자리 수 구하기
            for(int d=0; d<4; d++){
                int nx = x + dx[d];
                int ny = y + dy[d];
                if(nx<=0 || nx>N || ny<=0 || ny>N) continue;
                if(room[ny][nx] == 0) new_seat.hole ++;
                else{
                    for(int i=0; i<4; i++){
                        if(room[ny][nx] == st.like[i]){
                            new_seat.like++;
                            break;
                        }
                    }
                }
            }
            //2. 자리 후보 우선순위 큐에 추가
            pq.push(new_seat);
        }
    }
    //자리 선정
    seat = pq.top();
    room[seat.y][seat.x] = st.s_id;
}

void get_satisfy(){
    for(int y=1; y<=N; y++){
        for(int x=1; x<=N; x++){
            int s_id = room[y][x];
            int cnt = 0;
            //인접한 좋아하는 친구 수 카운트
            for(int d=0; d<4; d++){
                int nx = x+dx[d];
                int ny = y+dy[d];
                if(nx<=0 || nx>N || ny<=0 || ny>N) continue;
                for(int i=0; i<4; i++){
                    if(room[ny][nx] == students[s_id].like[i]){
                        cnt++;
                        break;
                    }
                }
            }
            if(cnt == 0) continue;
            satisfy += pow(10, cnt-1);
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> N;
    for(int i=1; i<=N*N; i++){
        cin >> st.s_id >> st.like[0] >> st.like[1] >> st.like[2] >> st.like[3];
        students[st.s_id] = st;
        cmds.push_back(st);
    }
    //모든 학생을 자리에 앉힌다
    for(int i=0; i<cmds.size(); i++){
        st = cmds[i];
        find_seat(st);
    }
    //만족도 구하기
    get_satisfy();
    cout << satisfy << endl;
    
    return 0;
}

---

풀이 과정

풀이 시간 38분

 

#include <iostream>
#include <math.h>
#include <vector>
#include <queue>
using namespace std;

int N;
int room[21][21] = {0, };

struct Student{
	//학생 번호
    int s_id;
    //좋아하는 4명의 학생 번호를 담는 배열
    int like[4] = {0, };
};
Student st;
//students[i] = i번 학생의 정보
Student students[401];
//자리 선정 순서를 담는 벡터
vector<Student> cmds;

struct Seat{
    int x;
    int y;
    //인접한 빈자리 수
    int hole = 0;
    //인접한 좋아하는 학생 수
    int like = 0;
};
Seat seat;
struct cmp{
    bool operator()(Seat s1, Seat s2){
    	//인접한 좋아하는 학생 수가 같은 경우,
        if(s1.like == s2.like){
        	//인접한 빈자리 수가 같은 경우,
            if(s1.hole == s2.hole){
            	//행 번호가 같은 경우,
                if(s1.y == s2.y){
                	//열 번호가 작은 순서대로
                    return s1.x > s2.x;
                }
                //행 번호가 작은 순서대로
                return s1.y > s2.y;
            }
            //인접한 빈자리가 많은 순서대로
            return s1.hole < s2.hole;
        }
        //인접한 좋아하는 학생 수가 많은 순서대로
        return s1.like < s2.like;
    }
};
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

//만족도의 총 합
int satisfy = 0;

void find_seat(Student st){
	//후보 자리를 우선순위에 따라 정렬하는 큐
    priority_queue<Seat, vector<Seat>, cmp> pq;
    
    for(int y=1; y<=N; y++){
        for(int x=1; x<=N; x++){
        	//빈 자리가 아닌 경우, 학생 st의 자리 후보가 될 수 없다
            if(room[y][x] > 0) continue;
            
            //빈 자리인 경우, 새로운 자리 후보이다
            Seat new_seat;
            new_seat.x = x;
            new_seat.y = y;
            //1. 인접한 좋아하는 학생 수와 빈자리 수 구하기
            for(int d=0; d<4; d++){
                int nx = x + dx[d];
                int ny = y + dy[d];
                //범위를 벗어난 경우, 무시한다
                if(nx<=0 || nx>N || ny<=0 || ny>N) continue;
                
                //빈 자리인 경우, 빈자리 수 카운팅
                if(room[ny][nx] == 0) new_seat.hole ++;
                
                //다른 학생이 앉아있는 경우, 학생 st가 좋아하는 학생인지 탐색
                else{
                    for(int i=0; i<4; i++){
                    	//좋아하는 학생인 경우, 좋아하는 학생 수 카운팅
                        if(room[ny][nx] == st.like[i]){
                            new_seat.like++;
                            break;
                        }
                    }
                }
            }
            //2. 해당 자리 후보 우선순위 큐에 추가
            pq.push(new_seat);
        }
    }
    //자리 선정
    seat = pq.top();
    room[seat.y][seat.x] = st.s_id;
}

void get_satisfy(){
	//모든 자리 탐색
    for(int y=1; y<=N; y++){
        for(int x=1; x<=N; x++){
        	//s_id = (x, y)에 앉아있는 학생 번호
            int s_id = room[y][x];
            
            //인접한 좋아하는 친구 수 카운트
            int cnt = 0;
            for(int d=0; d<4; d++){
                int nx = x+dx[d];
                int ny = y+dy[d];
                //범위를 벗어난 경우, 무시한다
                if(nx<=0 || nx>N || ny<=0 || ny>N) continue;
                for(int i=0; i<4; i++){
                	//좋아하는 학생이 인접해 있다면, 카운팅
                    if(room[ny][nx] == students[s_id].like[i]){
                        cnt++;
                        break;
                    }
                }
            }
            //인접한 좋아하는 친구가 하나도 없다면 만족도 0
            if(cnt == 0) continue;
            //인접한 좋아하는 친구가 있는 경우, 만족도 계산
            satisfy += pow(10, cnt-1);
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> N;
    for(int i=1; i<=N*N; i++){
        cin >> st.s_id >> st.like[0] >> st.like[1] >> st.like[2] >> st.like[3];
        //학생 정보를 추가한다
        students[st.s_id] = st;
        cmds.push_back(st);
    }
    //모든 학생을 자리에 앉힌다
    for(int i=0; i<cmds.size(); i++){
        st = cmds[i];
        //현재 순서의 학생 st의 자리 선정 -> O(N^2logN)
        find_seat(st);
    }
    //만족도 구하기 -> O(N^2)
    get_satisfy();
    cout << satisfy << endl;
    
    return 0;
}
//시간복잡도 = O(N^2logN), 공간복잡도 = O(N^2)

---

이전 풀이

풀이 시간 2시간 5분

 

#상어 초등학교
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Seat{
    int x;
    int y;
    int like;
    int hole;
};
struct cmp{
    bool operator()(Seat a, Seat b){
        if(a.like == b.like){
            if(a.hole == b.hole){
                if(a.y == b.y){
                    return a.x > b.x;
                }
                return a.y > b.y;
            }
            return a.hole < b.hole;
        }
        return a.like < b.like;
    }
};
int N;
//좌, 상, 우, 하
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
//교실 자리 -> 자리에 배정된 학생 번호를 담는다.
int room[20][20] = {0,};
//자리 배정할 학생 순서 -> order[순서] = 학생 번호
int order_s[400] = {0, };
//학생이 좋아하는 학생의 번호들을 담은 배열
//st[학생 번호] = [번호1, 번호2, 번호3, 번호4]
int st[401][4] = {0,};
long long answer = 0;
int s_num = 0;
int cnt;
Seat s;
int main(int argc, const char * argv[]) {
    cin >> N;
    for(int i=0; i<N*N; i++){
        cin >> s_num;
        order_s[i] = s_num;
        for(int j=0; j<4; j++){
            cin >> st[s_num][j];
        }
    }
    //첫번째 순서인 학생은 (1, 1)에 배정
    room[1][1] = order_s[0];
    //두번째부터 마지막 학생까지 자리 배정
    for(int i=1; i<N*N; i++){
        //자리 탐색
	//cmp에 맞게 자리가 우선순위에 맞게 정렬된다.
        priority_queue<Seat, vector<Seat>, cmp> pq;
        for(int y=0; y<N; y++){
            for(int x=0; x<N; x++){
                //이미 배정된 자리
                if(room[y][x]!=0) continue;
                //빈 자리인 경우, 인접 자리 탐색
                s = {x, y, 0, 0};
                int nx, ny;
                for(int d=0; d<4; d++){
                    nx = x+dx[d];
                    ny = y+dy[d];
                    if(nx<0 || nx>N-1 || ny<0 || ny>N-1) continue;
                    //인접 자리가 빈칸인 경우
                    if(room[ny][nx] == 0){
                        s.hole++;
                    }
                    //인접 자리에 학생이 있는 경우
                    else{
                        //현재 학생이 좋아하는 학생인지 체크
                        for(int k=0; k<4; k++){
                            if(room[ny][nx] == st[order_s[i]][k]){
                                s.like++;
                                break;
                            }
                        }
                    }
                }
		//해당 자리를 우선순위 큐에 담는다.
                pq.push(s);
            }
        }
	//모든 자리 탐색 완료, 우선순위가 가장 높은 자리에 해당 학생을 배정
        room[pq.top().y][pq.top().x] = order_s[i];
    }
    //만족도 조사
    for(int y=0; y<N; y++){
        for(int x=0; x<N; x++){
            cnt = 0;
            s_num = room[y][x];
	    //인접한 자리에 좋아하는 학생이 몇 명 있는지 탐색
            for(int d=0; d<4; d++){
                int nx = x+dx[d];
                int ny = y+dy[d];
                if(nx<0 || nx>N-1 || ny<0 || ny>N-1) continue;
                for(int i=0; i<4; i++){
                    if(room[ny][nx] == st[s_num][i]){
                        cnt ++;
                        break;
                    }
                }
            }
	    //인접한 좋아하는 학생 수에 따라 만족도 더하기
            if(cnt == 1) answer++;
            else if(cnt == 2) answer += 10;
            else if(cnt == 3) answer += 100;
            else if(cnt == 4) answer += 1000;
        }
    }
    cout << answer << endl;
    return 0;
}
//시간복잡도 = (N^2logN), 공간복잡도 = O(N^2)