[백준] 상어 초등학교

유승선 ·2022년 7월 29일
0

백준

목록 보기
38/64

백준은 상어를 참 좋아하는거같다, 그리고 시뮬레이션 문제에서 얼마나 문제를 잘 읽어야 하는지 다시한번 깨닫게 해준 문제이다.

다른 상어 시리즈와는 다르게 이번 문제는 그래도 마음에 들었던게 예시를 더 디테일하게 주었단 것이다. 만약에 예시마저 대충 줬다면은 난 이 문제를 못풀었을것만 같은 느낌이었다. 문제 자체는 그렇게 어렵게 느껴지지는 않았지만 문제를 더 자세히 읽었으면 큰 스트레스 없이 잘 풀었을 느낌이긴 하다..

특이하게 일반적인 Matrix 문제가 아니고 학생의 번호가 따로 주어지고 좋아하는 학생의 번호를 따로 담아서 유지 해줬어야 했다. 인접한 자리를 구하는 공식을 내가 잘 안읽었어서 너무 뻘짓한 것도 있지만 다 채우고 나서는 괜찮았다.

이 문제에 가장 핵심이어야 했던 sort 알고리즘이었다. 해당 시뮬레이션에 맞게 정렬을 해줘야 한다는 디테일이 있었고 이 부분만 잘 통과했다면 사실상 어려운점은 크게 없었을것이다. 다만 내가 너무 뻘짓을 많이 해서 시간을 날린거만 빼면 괜찮았던 문제이다.

좀 맘에 안들었던거는 findfriend 를 내가 너무 수동적으로 할려고 했던거같은데 Map 을 썼다면 훨씬 간단했을것만 같은 기분이다.

#include <iostream> 
#include <bits/stdc++.h> 
#define endl "\n"
#define MAX 100010
using namespace std;

int N; 
int matrix[21][21]; 
vector<vector<int>> friendLst; 
vector<pair<int,int>> dir = {{1,0},{-1,0},{0,-1},{0,1},{1,-1},{1,1},{-1,-1},{-1,1}}; 

void Input(){
    cin >> N; 
    for(int i = 0; i < pow(N,2); i++){
        int a, b, c, d, e; 
        cin >> a >> b >> c >> d >> e; 
        friendLst.push_back({a,b,c,d,e}); 
    }
}

bool findfriend(int target, int index){
    for(int i = 1; i < friendLst[index].size(); i++){
        if(friendLst[index][i] == target){
            return true;
        }
    }
    return false; 
}

vector<int> find(int x, int y, int index){
    vector<int> ret(4,0); 
    ret[2] = x;
    ret[3] = y; 
    for(pair<int,int>& p : dir){
        int nx = x + p.first;
        int ny = y + p.second; 

        if(nx < 0 || ny < 0 || nx >= N || ny >= N || (abs(x-nx) + abs(y-ny)) != 1) continue; 

        if(matrix[nx][ny] == -1) ret[0]++; //빈칸일때 
        else if(findfriend(matrix[nx][ny],index)) ret[1]++; //친구 목록에 포함이 될때
    }
    return ret; 
}

int calculate(int num){
    if(num == 0) return 0;
    if(num == 1) return 1;
    if(num == 2) return 10;
    if(num == 3) return 100;
    return 1000; 
}

void Solution(){
    memset(matrix,-1,sizeof(matrix)); 
    vector<vector<int>> candidates; 
    int answer = 0; 
    for(int index = 0; index < friendLst.size(); index++){
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(matrix[i][j] == -1){ //빈칸일 경우에만 
                    candidates.push_back(find(i,j,index)); 
                }
            }
        }
        //조건에 맞게 정렬 
        sort(candidates.begin(),candidates.end(),[](vector<int>& a, vector<int>& b){
            if(a[1] == b[1]){
                if(a[0] == b[0]){
                    if(a[2] == b[2]){
                        return a[3] < b[3]; 
                    }
                    return a[2] < b[2];
                }
                return a[0] > b[0]; 
            }
            return a[1] > b[1]; 
        });
        matrix[candidates[0][2]][candidates[0][3]] = friendLst[index][0]; 
        candidates.clear(); 

    }

    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            vector<int> check; 
            for(int k = 0; k < friendLst.size(); k++){
                if(friendLst[k][0] == matrix[i][j]){
                    check = (find(i,j,k));
                    answer += calculate(check[1]); 
                    break; 
                }
            }
        }
    }


    cout << answer; 
}


void Solve(){
    Input();
    Solution(); 
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("input.txt", "r", stdin);
    Solve();
    return 0;

}

배운점:
1. Simulation 에서 실수하지 말자
2. 조그만한것도 다시 확인해보자..

profile
성장하는 사람

0개의 댓글