[백준 9938] 방 청소

알고리즘 문제풀이/백준

[백준 9938] 방 청소

홍시홍 2020. 1. 9. 21:29

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

9938번: 방 청소

문제 은기는 술병 N개(1부터 N까지 번호가 매겨져 있다)와 서랍 L개(1부터 L까지 번호가 매겨져 있다)를 가지고 있다. 술병은 은기의 방 바닥에 흩어져 있고, 어린이날을 맞이해 방 청소를 하려고 한다. 서랍에는 술병이 하나 들어갈 수 있다. 나중에 원하는 술을 빠르게 찾을 수 있게 하기 위해 은기는 각각의 술병이 들어갈 수 있는 서랍의 번호 Ai와 Bi를 공책에 적어 놓았다. 은기는 술병을 1번부터 N번까지 순서대로 정리할 것이고, 각각의 술병에 대

www.acmicpc.net

1/6일날 풀었던 문제

요구사항

1. 빈 서랍에 술을 저장할 수 있나 없나에 대해 답을 하는 문제

풀이

1. 주어지는 입력을 통로라고 생각하고 하나로 쭉 이어준다

2. 적합한 자료구조인 Union-Find 사용한다.

#include <stdio.h>
#include <algorithm>
#include <list>
#include <iostream>

using namespace std;
 
struct NODE {
    int prev;
    int next;
    int val;
};
const int PN=23;
const int SIZE=100000;
int table[100001];
bool visit[300001];
int parent[300001];
int Find(int x)
{
    if(parent[x]==x) return x;
    return parent[x]=Find(parent[x]);
}
void Union(int x, int y)
{
    x = Find(x);
    y = Find(y);
    parent[x]=y;
}

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1; i <=m ; i++){
        parent[i]=i;
    }

    for(int i=1 ; i <= n ; i++){
        int x,y;
        scanf("%d%d",&x,&y);
        if(!visit[x]){
            visit[x]=true;
            Union(x,y);
            printf("LADICA\n");
        }
        else if(!visit[y]){
            visit[y]=true;
            Union(y,x);
            printf("LADICA\n");
        }
        else if(!visit[Find(x)]){
            visit[Find(x)]=true;
            Union(x,y);
            printf("LADICA\n");
        }
        else if(!visit[Find(y)]){
            visit[Find(y)]=true;
            Union(y,x);
            printf("LADICA\n");
        }
        else{
            printf("SMECE\n");
        }
    }
}