KOI 2017 고등부 전체 풀이

BOJ 14867 고등부 1번 물통 

문제 링크 : https://www.acmicpc.net/problem/14867

문제 태그

bfs

문제 풀이

우리는 문제를 풀 때 항상 '상태'라는 것에 집중을 해야한다. 이번 문제에서는 문제의 디스크립션에서부터 이에 대한 언급을 해준다. 어떤 상태에서는 문제에서 주어진 행동을 할 수 있으며, 따라서 갈 수 있는 다음상태가 정해져 있다.

여기서 좀 생각을 해보면, 이를 그래프로써 표현하여 bfs로 문제를 해결할 수 있다. 각 상태가 그래프의 정점이 되며, 갈 수 있는 다음 상태(노드)들을 방향 간선으로 연결함으로써 그래프 문제로 옮길 수 있다. 이 과정에서 만약 (i,j) 를 1번 물통에 찬 물의 양이 i, 2번 물통에 찬 물의 양이 j로 생각해서 푼다면 한 가지 걸리는 점이 생긴다. 바로 공간복잡도의 제약이 걸리게 된다. 따라서 우리는 이를 최적화 할 방법을 찾아야 한다. 

관찰을 한가지 해보자. 가능한 3가지 행동 중 어떤 행동인가를 한 뒤에는 어떤 상황일까? 즉 다시 말해 가능한 상태는 무엇일까? 이에 대한 답은 어떤 물통은 비어있거나 꽉 차있는 상태라고 할 수 있다. 좀만 관찰하면 알 수 있을것이다. 따라서 (i,j)로 가능하지도 않은 상태를 포함하기 보다는
(1,j)는 1번 물통은 꽉 차있고, 2번 물통에 물이 j만큼 담겨있는 상태
(2,j)는 1번 물통은 비어있고, 2번 물통에 물이 j만큼 담겨있는 상태
(3,j)는 2번 물통은 꽉 차있고, 1번 물통에 물이 j만큼 담겨있는 상태
(4,j)는 2번 물통은 비어있고, 1번 물통에 물이 j만큼 담겨있는 상태
로 나타내면 훨씬 공간을 아낄 수 있고, 이렇게 나타낸 경우에는 문제를 해결할 수 있다.

코드

2년전에 짠 문제이기 때문에 코드가 굉장히 더러울 수 있다.

#include<bits/stdc++.h>
using namespace std;

int vis[10][1010101];
int a,b,c,d;

void bfs()
{
    queue<int> qa,qb,dep;
    vis[1][0]=1;
    vis[3][0]=1;
    qa.push(0);
    qb.push(0);
    dep.push(1);
    while(!qa.empty())
    {
        int aa=qa.front(); qa.pop();
        int bb=qb.front();  qb.pop();
        int dept=dep.front(); dep.pop();
        if(vis[1][bb]==0)
        {
            qa.push(0);
            qb.push(bb);
            dep.push(dept+1);
            vis[1][bb]=dept+1;
        }
        if(vis[2][bb]==0)
        {
            qa.push(a);
            qb.push(bb);
            dep.push(dept+1);
            vis[2][bb]=dept+1;
        }
        if(vis[3][aa]==0)
        {
            qa.push(aa);
            qb.push(0);
            dep.push(dept+1);
            vis[3][aa]=dept+1;
        }
        if(vis[4][aa]==0)
        {
            qa.push(aa);
            qb.push(b);
            dep.push(dept+1);
            vis[4][aa]=dept+1;
        }
        if(aa!=0)
        {
            if(aa+bb<=b&&vis[1][aa+bb]==0)
            {
                qa.push(0);
                qb.push(aa+bb);
                dep.push(dept+1);
                vis[1][aa+bb]=dept+1;
            }
            else if(aa+bb>b&&vis[4][aa+bb-b]==0)
            {
                qa.push(aa+bb-b);
                qb.push(b);
                dep.push(dept+1);
                vis[4][aa+bb-b]=dept+1;
            }
        }
        if(bb!=0)
        {
            if(aa+bb<=a&&vis[3][aa+bb]==0)
            {
                qa.push(aa+bb);
                qb.push(0);
                dep.push(dept+1);
                vis[3][aa+bb]=dept+1;
            }
            else if(aa+bb>a&&vis[2][aa+bb-a]==0)
            {
                qa.push(a);
                qb.push(aa+bb-a);
                dep.push(dept+1);
                vis[2][aa+bb-a]=dept+1;
            }
        }
    }
}


int main()
{
    int i,j,k,l,m,n,mini=1e9;
    scanf("%d %d %d %d",&a,&b,&c,&d);
    bfs();
    if(c==0)
        mini=min(mini,vis[1][d]);
    if(d==0)
        mini=min(mini,vis[3][c]);
    if(c==a)
        mini=min(mini,vis[2][d]);
    if(d==b)
        mini=min(mini,vis[4][c]);
    if(mini==1e9)
        printf("-1");
    else printf("%d",mini-1);
}

BOJ 14868 고등부 2번 문명

문제 링크 : https://www.acmicpc.net/problem/14868

문제 태그

union & find , dfs(?)

문제 풀이

일단 딱 문제를 보면 전체를 합쳐나가는 것이다. 그 과정에서 편하게 하기 위해서 현재 어떠한 그룹들이 합쳐져 있는지를 생각해 봐야하는 데 이를 관리하기 위해서는 union & find 가 필요하다.
이 문제를 풀기 위해서 임의의 두 문명에 대해서 그 두 문명이 언제 결합될지를 다 알고 싶다 하지만 그렇게 구하는 경우 시간 복잡도가 $O(K^2)$이므로 시간초과가 나게 된다. 하지만 다른 제한에 눈을 돌린다면 지도의 한변 길이는 2000으로 굉장히 작다는 것을 알 수 있고, 지도 전체를 한번씩 덮어도 TLE가 나지 않는다는 것을 알 수 있다. 따라서 bfs인지 dfs인지를 이용해서 실제로 지도의 칸을 덮어가며 만날 때마다 union을 해주면 된다. 사실 관찰보다는 사전지식과 구현문제에 가깝다. 

코드

2년전에 짠 문제이기 때문에 코드가 굉장히 더러울 수 있다.(수 있는것이 아니라 실제로 많이 역겹다.)

#include <bits/stdc++.h>
using namespace std;

int mapp[2020][2020];
int par[101010];
int num[101010];
int arr1[4]={-1,0,1,0};
int arr2[4]={0,1,0,-1};
int n,k;

struct poi{
    int x;
    int y;
};

poi civ[101010];

int uf(int a)
{
    if(par[a]==a)
        return a;
    if(par[a]==0)
    {
        par[a]=a;
        return a;
    }

    par[a]=uf(par[a]);

    return par[a];

}

bool mergee(int a,int b)
{
    a=uf(a);
    b=uf(b);
    if(a==b) return false;
    if(num[a]>num[b])
    {
        par[b]=a;
    }
    else if(num[a]<num[b])
    {
        par[a]=b;
    }

    if(num[a]==num[b])
    {
        par[a]=b;
        num[b]++;
    }
    return true;
}


int main()
{
    int h=0,i=0,j=0,k=0;
    int xx=0,yy=0;
    int moxx=0,moyy=0;
    int this_mun=0,mun=0;
    int chk=0,cnt=0;
    int have_parent=0;
    poi timun;

    scanf("%d %d",&n,&k);

    queue<poi> q;
    queue<poi> semiq;

    for(i=1;i<=k;i++)
    {
        mun++;
        scanf("%d %d",&civ[i].x,&civ[i].y);
        mapp[civ[i].x][civ[i].y]=mun;
        q.push(civ[i]);
    }


    for(i=0;i<=n;i++)
    {
    while(!q.empty())
    {
        xx=q.front().x;
        yy=q.front().y;

        this_mun=mapp[xx][yy];

        for(j=0;j<4;j++)
        {
            moxx=xx+arr1[j];
            moyy=yy+arr2[j];
            if(1<=moxx&&moxx<=n&&1<=moyy&&moyy<=n)
                if(mapp[moxx][moyy]!=0&mapp[moxx][moyy]!=this_mun)
                    if(mergee(mapp[moxx][moyy],this_mun))
                        have_parent++;
        }

        semiq.push(q.front());
        q.pop();

        if(have_parent==k-1)
        {
            printf("%d",cnt);
            return 0;
        }


    }
        for(j=0;j<semiq.size();)
        {
            xx=semiq.front().x;
            yy=semiq.front().y;
            this_mun=mapp[xx][yy];

            for(h=0;h<4;h++)
            {
                moxx=xx+arr1[h];
                moyy=yy+arr2[h];
                if(1<=moxx&&moxx<=n&&1<=moyy&&moyy<=n&&mapp[moxx][moyy]==0)
                {
                    mapp[moxx][moyy]=this_mun;
                    timun.x=moxx;
                    timun.y=moyy;
                    q.push(timun);
                }
            }
            semiq.pop();
        }
        cnt++;
    }
}

BOJ 14869 고등부 3번 요리강좌

쓰다보니까 너무 길고, 꽤나 중요한 문제라서  포스팅을 따로 작성하려고 한다.

링크는 https://stonejjun.tistory.com/100

BOJ 148670 고등부 4번 조개줍기

이 문제도 하고 싶은 말들이 많기 때문에 포스팅을 따로 작성하려고 한다. 

링크는 https://stonejjun.tistory.com/101