티스토리 뷰

 

문제가 좀 복잡해 보이는데 잘 읽어보면 dfs를 이용해서 풀 수 있다

먼저 입력으로 들어오는 이름들은 map을 통해 숫자롤 매겨주자

 

그리고 시너지가 발생하는 조합을 통해 그래프를 만들어준다

 

그래프를 다 만들었다면

이제 문제는 나와 연결된 정점과 다른색으로 색칠하며 dfs를 돌릴 수 있냐!

이걸로 바뀌게 된다

 

나와 연결된 정점들에 나와 다른색을 주면서 dfs를 돌아보자

만약 같은색이 있다면 false! 다 돌수 있다면 true 다

 

하나라도 false가 나오면 No가 답이다

 

 

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
int t,k;
 
bool check[222];
int color[222];
bool solve(vector<vector<int>>& Graph,int pos){
    check[pos]=true;
    for(int i=0;i<Graph[pos].size();i++){
        int next = Graph[pos][i];
        if(color[next]==color[pos]) return false;
        if(!check[next]) {
            color[next]=!color[pos];
            if(!solve(Graph,next)) return false;
        }
    }
    return true;
}
int main(){
    scanf(" %d",&t);
    for(int tc=1;tc<=t;tc++){
        memset(check,0,sizeof(check));
        memset(color,-1,sizeof(color));
        scanf(" %d",&k);
        int pos=0;
        map<string,int> mp;
        vector<pair<int,int>> vt;
        for(int i=0;i<k;i++){
            string a,b; cin>>a>>b;
            if(!mp.count(a)) mp[a]=pos++;
            if(!mp.count(b)) mp[b]=pos++;
            vt.push_back({mp[a],mp[b]});
        }
        vector<vector<int>> Graph(pos);
        for(int i=0;i<k;i++){
            int x=vt[i].first;
            int y=vt[i].second;
            Graph[x].push_back(y);
            Graph[y].push_back(x);
        }
        
        bool ans=true;
        for(int i=0;i<pos;i++){
            if(!check[i]){
                color[i]=0;
                ans&=solve(Graph,i);
            }
        }
        printf("#%d %s\n",tc,(ans) ? "Yes" : "No"); 
    }
}
 
 

'알고리즘 > SW Expert Academy' 카테고리의 다른 글

[SWEA] 7396 종구의 딸 이름 짓기  (0) 2020.03.06
[SWEA] 5684 운동  (0) 2020.03.05
[SWEA] 8275 햄스터  (0) 2020.03.04
[SWEA] 1907 모래성 쌓기  (0) 2020.03.03
[SWEA] 8382 방향전환  (0) 2020.03.03
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG
more
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함