문제 : boj1953
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
필요 알고리즘
- 이분 그래프 (bipartite graph), 그래프 탐색 (BFS, DFS 등)
- 이분 그래프에 대한 개념이 있다면 좀 더 쉽게 풀 수 있는 그래프 탐색 문제이다.
※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.
풀이
2년전에 못 푼 기록이 있어 풀어봤다. 별 어려움 없이 바로 푼걸 보면 발전은 있었나보다. 2년전엔 HashSet을 사용해 넣을 때 마다 겹치는게 있는지 검색해본 것 같다. 이런방식으론 당연히 풀기 어려웠을 것 같다.
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
이번에 문제의 경우 풀이는 지문의 "팀을 나누는 것이 불가능 한 경우는 없다고 하자." 라는 부분을 보고 떠올랐다. 이 말은 서로 싫어하는 사람들끼리 간선을 연결해 그래프로 나타냈을 때, 아래와 같은 경우는 입력되지 않는다는 얘기이다. (1과 2가 서로 싫어하고, 2와 3이 싫어하고, 3과 1이 서로 싫어하면 팀을 2개로 나누는 것이 불가하다.)
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
즉, 알고리즘으로 얘기해보자면, "주어진 입력값은 반드시 이분 그래프"라는 말이다. 이분 그래프가 무엇인지 모른다면 '이분 그래프 (bitartite graph)' 글을 확인해보자. 그럼 이 문제는 "이분 그래프가 주어진다. 정점을 두 개의 집합으로 나눠라" 라는 문제가 되며, 이건 이하의 로직으로 풀 수 있다.
1. 아직 방문하지 않은 정점을 아무데나 방문한다.
2. 해당 정점을 둘 중 아무 팀에나 넣는다.
3. 인접한 정점을 방문한다. 이 때, 인접한 정점끼리는 서로 다른 팀에 넣는다.
4. '3'을 반복하다가, 인접한 곳이 없다면 '1'로 다시 돌아간다. 방문한 정점이 없어질때까지 계속하면 된다.
예를들어 예제 입력 1을 그래프로 나타내보면 다음과 같다.
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
- 우선 아직 방문하지 않은 곳을 아무 곳이나 방문한다. '1'을 방문하겠다. 그리고 아무 팀이나 넣는다. 청팀에 넣어도 되고, 백팀에 넣어도 된다.
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
- '1'과 인접한 정점을 방문한다. '1'이랑 다른 팀에다 넣으면 된다.
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
- '3'과 인접한 정점을 방문한다. 역시 '3'이랑 다른 팀에만 넣으면 된다.
![](https://blog.kakaocdn.net/dn/lML4x/btsFgpG6odX/WkqhTpP6a0u25eOngoJAI0/img.png)
- 이제 다시 방문하지 않은 곳 중에 아무 곳이나 방문한다. 이번엔 '5'를 방문해보자. 역시 아무 팀에나 넣으면 되며, 이번엔 백팀에 넣어보겠다.
![](https://blog.kakaocdn.net/dn/pfy1n/btsFiu1FwIJ/68ivL7oS4IZVGKQr00PIEk/img.png)
- '5'랑 인접한 정점을 방문하고, '5'랑 다른 팀에 넣으면 된다.
![](https://blog.kakaocdn.net/dn/qo8Xa/btsFjIL74mi/gMntuTt3TvhaLvPctVVYw1/img.png)
- 최종적으로 나뉜 두 팀을 정렬 후 출력하면 된다. 또, 위에서 얘기했던 로직에만 맞으면, 어떤 팀으로 나누는지는 상관 없다. 즉, 아래처럼 나누어도 이것도 답이다.
![](https://blog.kakaocdn.net/dn/nS2H0/btsFlOkOI80/KT69rtu1GrEFb7OLMGQAgk/img.png)
위의 과정을 반복해주면 되며, 위의 방법이 통하지 않는 경우가 있다면 문제 입력값이 잘못된 경우이므로 생각하지 않아도 된다.
코드 : github
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);
public static void main(String[] args) throws Exception {
new Main().solution();
}
public void solution() throws Exception {
int n = Integer.parseInt(br.readLine());
List<Integer>[] edges = new List[n+1];
for (int i = 1; i <= n; i++) {
edges[i] = new ArrayList<>();
}
for (int i = 1; i <= n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int cnt = Integer.parseInt(st.nextToken());
while (cnt-->0) {
int cur = Integer.parseInt(st.nextToken());
edges[i].add(cur);
edges[cur].add(i);
}
}
List<Integer> team1 = new ArrayList<>();
List<Integer> team2 = new ArrayList<>();
int[] v = new int[n+1];
for (int i = 1; i <= n; i++) {
if (v[i] != 0) continue;
v[i] = 1;
team1.add(i);
Queue<Integer> q = new ArrayDeque<>();
q.add(i);
while (!q.isEmpty()) {
int cur = q.poll();
for (int next : edges[cur]) {
if (v[next] != 0) continue;
if ((v[next] = 3-v[cur])==1) team1.add(next);
else team2.add(next);
q.add(next);
}
}
}
if (team2.isEmpty()) {
team1.remove(0);
team2.add(1);
}
Collections.sort(team1);
Collections.sort(team2);
StringBuilder sb = new StringBuilder();
sb.append(team1.size()).append('\n');
for (int cur : team1) {
sb.append(cur).append(' ');
}
sb.append('\n');
sb.append(team2.size()).append('\n');
for (int cur : team2) {
sb.append(cur).append(' ');
}
System.out.println(sb);
}
}
'PS > BOJ' 카테고리의 다른 글
[자바] 백준 14503 - 로봇 청소기 (java) (0) | 2024.03.19 |
---|---|
[자바] 백준 19953 - 영재의 산책 (java) (0) | 2024.03.18 |
[자바] 백준 16935 - 배열 돌리기 3 (java) (0) | 2024.02.26 |
[자바] 백준 17436 - 소수의 배수 (java) (0) | 2024.02.24 |
[자바] 백준 24956 - 나는 정말 휘파람을 못 불어 (java) (0) | 2024.02.24 |
댓글