조건이 다음과 같을때
1. 내 친구는 우리 편이다.
2. 내 친구의 친구는 우리 편이다.
3. 내 원수는 우리 편이 아니다.
4. 내 원수의 원수는 우리 편이다.
친구들의 관계가 주어지면 최대 몇 팀이 만들어질 수 있는지 알아내는 문제이다.
처음에는 단순하게
1. i : 1~n까지 노드를 돌며 bfs를 돌린다
(1) i 노드를 방문한 적이 없다면 1로 칠하고 친구라면 d[nx] = d[x], 적이라면 d[nx] = d[1-x] bfs를 돈다.
(2) 결과 팀이 2개로 나뉘었는가
- 친구만으로 이루어진 집단이라면 해당 노드에서 수행된 bfs로 인해 i번 노드에서 뻗어나간 간선의 목적지는 모두 1로 칠해졌을 것이고
- 적이 존재하는 집단이라면 0으로 칠해진 노드가 있을 것이다. check[2]배열로 확인한 후 ans += check[0] + check[1]
라고 생각했다. 하지만 18%즈음 WA를 받았다. 질문에도 관련질문이 없어서 해당 대회의 input을 찾아서 돌려봤더니 노드가 수백개가 넘어가는 케이스에서 답이 잘못나오더라. 뭔가 조건을 잘못 해석했다 싶어서 다시 생각을 해 보았다.
1. 내 친구는 우리 편이다. = 동일
2. 내 친구의 친구는 우리 편이다. = 동일. 친구 관계인 경우 타고들어갔을 때 모두가 친구인건 명확했다.
3. 내 원수는 우리 편이 아니다. = 동일
4. 내 원수의 원수는 우리 편이다.
-> 이 말을 "나는 내 원수가 속한 집단의 원수는 우리편이다."라고 생각하고 풀었다. 하지만 과연 그럴까. '내 원수'의 원수 라는 말이 중요한 것 같았다.
이전의 인식과의 차이점을 설명하자면
<-> : 적
= : 친구
1 <-> 2 = 3 <-> 4
를 이전에는 1과 4를 같은 팀으로 인식해서 팀을 2개로 나눈 반면 후자로 해석했을 때는 { 1 , {2,3}, 4 } 로 나뉘어 총 3개의 팀이 나온다. 1과 4가 친구일 수도 있다. 하지만 문제는 "명확히 알려진" n명의 사람간의 관계가 m개 주어졌을 때 최대 몇 팀이 만들어지는가를 요구하고 해당 방법은 최대를 출력하지 않는다. 그래서 후자의 방식으로 하니 AC를 받았다.
테스트 케이스를 만들어 디버깅 해보니 차이점이 명확히 보였다.
12
11
F 1 2
E 2 5
F 5 6
E 6 7
E 1 3
E 1 4
F 3 8
F 4 9
E 8 10
E 9 11
E 2 12
AC = 6
WA = 2
9
8
E 1 2
E 1 3
E 2 4
E 2 5
E 4 6
F 6 7
E 7 8
E 8 9
AC = 3
WA = 2
직접 관계도를 그리면서 해보거나 디버깅 해보면 차이점이 눈에 보인다..
* 원문에서는 모순되는 입력이 없다고 명시되어 있으나 번역문에는 누락되어 있다. 친구면서 동시에 적인 관계가 존재 할 수 없다는 뜻.
<코드>
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 | #include<stdio.h> #include<queue> #include<cstring> #include<vector> #include<algorithm> using namespace std; int n, m, r, c, d[1001], cnt; queue<int> q; vector<int> a[1001]; // 적인 간선만 따라간다. bool dfs(int prev, int x) { bool f = false; for (auto i : a[x]) if (i < 0 && d[-i] == -1) { f = true; d[-i] = prev; dfs(d[x], -i); } return f; } // 친구들 묶어주기용. void bfs(int x) { q.push(x); while (q.size()) { int nx = q.front(); q.pop(); for (auto i : a[nx]) if (i > 0 && d[i] == -1) { d[i] = d[nx]; q.push(i); } } } int main() { memset(d, -1, sizeof(d)); scanf("%d%d", &n, &m); while (m--) { char s; scanf(" %c%d%d", &s, &r, &c); if (s == 'E') a[r].push_back(-c), a[c].push_back(-r); else a[r].push_back(c), a[c].push_back(r); } for (int i = 1; i <= n; i++) { if(d[i] == -1) d[i] = ++cnt; cnt += dfs(cnt + 1, i); bfs(i); } printf("%d\n", cnt); return 0; } | cs |