프로그래밍

www.acmicpc.net/problem/19238

[난이도] Gold4

[유형] BFS, Simulation (삼성SW기출)

[풀이] 

1. y시작,x시작,y종료,x종료,현재 택시위치에서의 거리 d 이 5가지를 저장하는
구조체 P를 정의한다.
2. vector<P> s를 정의 M개의 P를 저장한다.
3. M회 루프를 돌면서 매 시행마다 s를 정렬해준다. 정렬은 comparator 를
   재정의하는 방식으로 한다. 거리,y좌표,x 우선순위로 정렬하면 항상
   s[0]이 지금 태우러 가야하는 사람이다. 뽑은 뒤 s[0]은 필요없으므로
   벡터에서 지워준다.
4. 벽에 의해 택시로 도달할 수 없는 사람이 있는 겨우와, 연료를 다쓰는 경우를
   예외처리 해준다.

#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
struct P{
    int y,x,ey,ex,d;
};
vector<P> s;
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,1,-1};
int N,M,K,map[21][21],py,px,INF=9e8;
bool visit[21][21];
int bfs(int y,int x){
    memset(visit,0,sizeof(visit));
    queue<P> q;
    q.push({y,x});
    visit[y][x] = 1;
    int ret = 0;
    while(!q.empty()){
        int sz = q.size();
        while(sz--){
            P qf = q.front(); q.pop();
            if(qf.y==py&&qf.x==px) return ret;
            for(int i=0;i<4;i++){
                int ny = qf.y+dy[i];
                int nx = qf.x+dx[i];
                if(ny < 1 || nx < 1 || ny > N || nx > N || map[ny][nx]) continue;
                if(!visit[ny][nx]){
                    q.push({ny,nx});
                    visit[ny][nx] = 1;
                }
            }
        }
        ret++;
    }
    return INF;
}
bool cmp(P& a,P& b){
    if(a.d < b.d) return 1;
    else if(a.d==b.d){
        if(a.y<b.y) return 1;
        else if(a.y==b.y) return a.x < b.x;
        return 0;
    }
    return 0;
}
int main(){
    scanf("%d%d%d",&N,&M,&K);
    s.resize(M);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++) scanf("%d",&map[i][j]);
    
    scanf("%d%d",&py,&px);
    for(int i=0;i<M;i++) scanf("%d%d%d%d",&s[i].y,&s[i].x,&s[i].ey,&s[i].ex);

    for(int i=0;i<M;i++){
        for(int j=0;j<s.size();j++) s[j].d = bfs(s[j].y,s[j].x);    
        sort(s.begin(),s.end(),cmp);
        P t = s[0];
        s.erase(s.begin());
        if(K-t.d < 0) {
            K=-1;
            break;
        }
        K-=t.d, py=t.y, px=t.x;

        int nDist = bfs(t.ey,t.ex);
        if(K-nDist < 0){
            K=-1;
            break;
        }
        py=t.ey, px=t.ex;
        K+=nDist;
    }
    printf("%d",K);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/19238.cpp

www.acmicpc.net/problem/17140

[난이도] Gold4

[유형] 시뮬레이션 (삼성SW기출)

[풀이]

R 연산에 대한 함수만 정의하고 배열을 반시계 방향으로 회전하는 함수를 들어서 이용하면 C 연산은 따로 정의하지 않아도 해결할 수 있다.

#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
using vvi = vector<vector<int>>;
int r,c,k;

vvi rot(vvi& m){
    int csz = m.size();
    int rsz = m[0].size();
    vector<vector<int>> ret(rsz,vector<int>(csz));
    for(int i=0;i<rsz;i++)
        for(int j=0;j<csz;j++) ret[i][j] = m[j][rsz-i-1];

    return ret;
}

vvi R(vvi& m){
    vvi tmp;
    int mxl = 0;
    for(auto v : m){
        map<int,int> cntMap;
        for(auto i : v) {
            if(i!=0) cntMap[i]++;
        }

        vector<pair<int,int>> ov;
        for(auto p : cntMap){
            ov.push_back({p.second,p.first});
        }
        sort(ov.begin(),ov.end());
        vector<int> res;
        for(auto o : ov){
            res.push_back(o.second);
            res.push_back(o.first);
        }
        mxl = max(mxl,(int)res.size());
        tmp.push_back(res);
    }
    mxl = min(100,mxl);
    for(auto& t : tmp) t.resize(mxl);
    return tmp;
}

int main(){
    scanf("%d%d%d",&r,&c,&k);
    r--,c--;
    vvi map;
    for(int i=0;i<3;i++){
        vector<int> a(3);
        for(int j=0;j<3;j++) scanf("%d",&a[j]);
        map.push_back(a);
    }
    int time = 0;
    while(1){
        int rsz = map.size();
        int csz = map[0].size();
        if(r < rsz && c < csz && map[r][c]==k) break;
        if(time==100){
            time = -1;
            break;
        }
        if(rsz >= csz){
            map = R(map);
        }else{
            map = rot(map);
            map = R(map);
            for(int i=0;i<3;i++) map=rot(map);
        }
        time++;
    }
    printf("%d",time);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/17140.cpp

www.acmicpc.net/problem/16235

[난이도] Gold4

[유형] 시뮬레이션 (삼성SW기출)

[풀이] 

우선순위 큐를 사용한 코드는 시간초과가 나서 vector+sort를 조합해서 A/C를 받았다. 나무가 생각보다 많이 만들어질 수 있어서 push,pop 과정에서 시간이 많이 드는 것 같다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N,M,K;
long long ans;
int dy[8] = {1,-1,0,0,1,1,-1,-1};
int dx[8] = {0,0,1,-1,1,-1,-1,1};
vector<long long> tree[101][101];;
int A[101][101],yb[101][101],seed[101][101];
void feed(int y,int x){
    auto& tr = tree[y][x];
    vector<long long> tt;
    int tyb=0;
    for(int i=0;i<tr.size();i++){
        int age = tr[i];
        if(yb[y][x] >= age){
            yb[y][x]-=age;
            tt.push_back(age+1);
        }else{
            tyb += age/2;
        }        
    }
    tr = tt;
    yb[y][x] += tyb;
}

void expd(int y,int x){
    auto& tr = tree[y][x];
    for(int i=0;i<tr.size();i++){
        int age = tr[i];
        if(age%5==0){
            for(int i=0;i<8;i++){
                int ny = y+dy[i];
                int nx = x+dx[i];
                if(ny < 1 || nx < 1 || ny > N || nx > N) continue;
                seed[ny][nx]++;
            }   
        }        
    }
}
int main(){
    scanf("%d%d%d",&N,&M,&K);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++) {
            scanf("%d",&A[i][j]);
            yb[i][j] = 5;
        }
    for(int i=0;i<M;i++){
        int y,x,z;
        scanf("%d%d%d",&x,&y,&z);
        tree[x][y].push_back(z);
    }
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++) sort(tree[i][j].begin(),tree[i][j].end());
        
    while(K--){
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                feed(i,j);
                seed[i][j]=0;
            }
        }
        for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++) expd(i,j);

        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                for(int k=0;k<seed[i][j];k++) tree[i][j].push_back(1);
                sort(tree[i][j].begin(),tree[i][j].end());
                yb[i][j] += A[i][j];
                if(K==0) ans += tree[i][j].size();
            }
        }
    }
    printf("%d",ans);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/16235.cpp

www.acmicpc.net/problem/15685

[난이도] Gold4

[유형] 시뮬레이션 (삼성SW기출)

[풀이]

시키는대로 하자

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int dy[4] = {0,-1,0,1};
int dx[4] = {1,0,-1,0};
int N;
bool map[102][102];
int main(){
    scanf("%d",&N);
    for(int dc=0;dc<N;dc++){
        int x,y,d,g;
        scanf("%d%d%d%d",&x,&y,&d,&g);
        vector<int> seq(1);

        for(int i=0;i<g;i++){
            int sz = seq.size();
            for(int j=sz-1;j>=0;j--) seq.push_back((seq[j]+1)%4);
        }
        map[y][x] = 1;
        for(int v : seq) {
            v=(v+d)%4;
            y+=dy[v];
            x+=dx[v];
            map[y][x] = 1;
        }
    }

    int ans = 0;
    for(int i=0;i<100;i++){
        for(int j=0;j<100;j++){
            if(map[i][j]&&map[i+1][j]&&map[i+1][j+1]&&map[i][j+1]) ans++;  
        }
    }
    printf("%d",ans);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/15685.cpp