[백준] BOJ 1733 등번호

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

 

 

| Solved.ac 난이도 : P1 |

 

문제 추천도 : 8/10

 

걸린 시간 : 52' 53''

 

 

🏷️ 그래프 탐색, DFS

이분 매칭 풀이도 존재하며 내 DFS 풀이보다 시간이 더 오래 걸려서 크기가 큰 테스트케이스가 추가된 재채점에서 TLE가 많이 생겨 W.A 처리가 된 코드가 많다. 이분 매칭 등의 더 난해한 풀이 때문에 난이도가 올려치기 되어있는 감이 있다.

+) 내 P3 기여로 문제 티어가 P2가 되었다.

 

---

 

 

풀이

 

$($관찰$)$ 1. 이런 류의 문제를 많이 풀어봤다면 직관적으로 "아, 이거 그래프로 바꿔서 풀어야겠구나!"를 문제를 읽자마자 알 수 있다.

 

2. 번호가 1,000,000까지의 수만 주어지므로, 각각 앞 번호와 뒷 번호를 정점으로 하는 간선을 만들어준다.

• 만약, 3명의 사람이 각각 {1 2}, {2 3}, {3 1}의 앞,뒷 번호의 티셔츠를 가지고 있다면, 그래프는 다음과 같이 만들어진다.
• 번호가 1~N이 아닌 1~1,000,000임에 유의해야 한다.

 

$($발상$)$ 3. 우리는 각 간선에 대한 답을 구해야 한다. 어떤 간선이 연결하는 두 정점 $u$ - $v$에서 간선에 대한 답은 $u$ 또는 $v$가 된다.

또한, 모든 간선에 대한 답에서 같은 정점이 두 번 이상 포함 될 수는 없다. $($같은 번호가 적힌 면을 두 명 이상의 사람이 입을 수 없다$)$

 

4. DFS를 돌리면서 답을 구해볼 것이다.

예시. 아래 설명 참고

• 현재 정점이 $b$인 상황에서 $a$로의 간선을 타고 가는데, $a$가 이미 방문한 정점이라면, $a$ - $b$ 간선의 답은 $b$가 되어야 한다. $($$b$가 이미 사용되었기 때문$)$ 해당 경우는 사이클이 발생하는 경우이다.
• 만약, 현재 정점 $d$에서 더 이상 이동할 간선이 없는 경우, 전에 $d$로 이동시킨 간선의 답을 $d$로 하자.  $c$에서 $d$로 이동했다고 하면, $c$도 답이 될 수 있지만, $d$에서 따로 이동할 간선이 없기 때문에 $d$가 최적임이 자명하다.

 

$($구현$)$ 5. 앞서 설명한대로 모든 정점이 방문될 때까지 DFS를 수행한다.  DFS를 돌던 중 사이클이 발생하거나, 더 이상 방문할 간선이 없다면 return 해준다.

이외의 경우, 어떤 정점과 연결된 간선에서 해당 정점을 답으로 가져야 하는 상황이 발생하면 return 한다. 나는 구현의 편의를 위해 DFS에서 해당 간선이 어떤 정점을 답으로 가지는지 return 해주면서 구현했다.

 

---

 

 

p.s) W.A에서 해매고 있는 분들을 위해 내가 사용한 반례 데이터를 첨부한다.

 

5

1 4
4 2
4 3
4 5
5 1

반례 데이터 1

 

5

1 3
3 5
3 4
1 2
4 5

반례 데이터 2

 

---

 

 

구현
라이트 모드로 보셔야 잘 보입니다

풀이를 이해하셨다면 구현은 직접 자신의 결로 써보시길 추천드립니다.

# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
# pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define fastio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
vector<pair<int,int>> v[1000010];
int n;
int ch_node[1000010];
int ch_road[1000010];
int dfs(int x,int p,int last)
{
    ch_node[x]=1;
    for(auto i:v[x])
    {
        if(ch_road[i.second] || last==i.second) continue;
        if(ch_node[i.first])
        {
            ch_road[i.second]=x;
            return p;
        }
        else
        {
            ch_road[i.second]=dfs(i.first,x,i.second);
            if(ch_road[i.second]==x)
                return p;
        }
    }
    return x;
}
int main()
{
    fastio;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int a,b;
        cin>>a>>b;
        v[a].push_back({b,i});
        v[b].push_back({a,i});
    }
    for(int i=1;i<=1000000;i++)
    {
        if(ch_node[i]==0)
            dfs(i,0,0);
    }
    vector<int> ans;
    int flag=0;
    for(int i=1;i<=n;i++)
    {
        if(ch_road[i]==0)
        {
            cout<<-1;
            return 0;
        }
        ans.push_back(ch_road[i]);
    }
    for(auto i:ans) cout<<i<<'\n';
}

 

그래프 제작 : https://csacademy.com/app/graph_editor