BOJ_17304_변호사들 (Java)
BOJ_17304_변호사들 (Java)
[Platinum II] 변호사들 - 17304
성능 요약
메모리: 94808 KB, 시간: 668 ms
분류
깊이 우선 탐색, 그래프 이론, 그래프 탐색, 강한 연결 요소
제출 일자
2024년 12월 17일 05:34:02
문제 설명
N명의 변호사가 사기 범죄를 저지른 혐의로 기소되었다. N명의 변호사는 서로를 변호하여 전원 무사히 무죄로 처리되려고 한다.
변호사들은 자신이 신뢰하는 변호사에게만 변호를 받을 수 있다. 이 신뢰관계란 M개의 (A, B)쌍으로 표현되는데, 이는 변호사 B가 변호사 A를 신뢰한다는 의미로 이 경우에만 변호사 A가 변호사 B를 변호할 수 있다.
각각의 변호사들의 실력은 매우 뛰어나기 때문에, 1명 이상의 변호를 받은 사람은 무조건 무죄가 된다. 단, 두 변호사 A, B에 대해 A가 B를 변호하고, B가 A를 변호하는 경우는 매우 수상하기 때문에 둘 모두 유죄가 된다.
각 (A, B) 쌍에 대해 변호사 A가 변호사 B를 변호할지 말지를 선택하여 모든 변호사가 무죄가 되는 것이 가능한지 판정하라.
입력
첫 줄에 N과 M이 주어진다. (1 ≤ N, M ≤ 200,000)
두 번째 줄부터 M 줄에 걸쳐 i번째 줄에는 서로 다른 두 정수 Ai, Bi가 주어진다. 이는 변호사 Ai가 변호사 Bi를 변호할 수 있다는 뜻이다.
주어지는 입력에서 순서쌍 (A, B)가 중복하여 나타나는 경우는 없다.
출력
모든 변호사가 1명 이상의 변호를 받고, 서로를 변호하는 변호사 쌍이 없도록 할 수 있는 경우 첫 줄에 YES을 출력한다.
불가능한 경우 첫 줄에 NO를 출력한다.
문제 풀이
처음 틀린 풀이(14%) 부터 리뷰하겠다.
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// 틀린풀이(14%)
/**
* Author: nowalex322, Kim HyeonJae
*/
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader br;
static BufferedWriter bw;
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
static int N, M;
static ArrayList<Integer>[] lawyer; // a->b 변호 관계
static ArrayList<Integer>[] canDefendMe; // 나를 변호할 수 있는 변호사 리스트
static boolean[] isDefended; // 변호받았는지 여부
static int[] defenderOf; // 각 변호사의 변호자 번호
public static void main(String[] args) throws Exception {
new Main().solution();
}
public void solution() throws Exception {
br = new BufferedReader(new InputStreamReader(System.in));
// br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_17304_변호사들/input.txt")));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
lawyer = new ArrayList[N + 1];
canDefendMe = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
lawyer[i] = new ArrayList<>();
canDefendMe[i] = new ArrayList<>();
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
lawyer[a].add(b);
canDefendMe[b].add(a);
}
isDefended = new boolean[N + 1];
defenderOf = new int[N + 1]; // 변호관계저장
Arrays.fill(defenderOf, -1);
for (int i = 1; i <= N; i++) {
if (!isDefended[i]) {
if (!dfs(i)) {
System.out.println("NO");
return;
}
}
}
System.out.println("YES");
bw.flush();
bw.close();
br.close();
}
static boolean dfs(int curr) {
if (isDefended[curr]) return true;
for (int defender : canDefendMe[curr]) {
if (lawyer[curr].contains(defender) && defenderOf[defender] == curr) continue;
// 아직 변호 못받은사람
if (defenderOf[defender] == -1 || dfs(defenderOf[defender])) {
isDefended[curr] = true; // curr이 변호받음
defenderOf[curr] = defender; // defender -> curr 변호
return true;
}
}
return false;
}
}
변호관계를 다 저장한 뒤 dfs로 그래프 탐색을 한다. 이때 양방향이거나 이미 변호 받았으면 넘어가고, 아직 변호 못 받은 사람(변호인이 변호한 사람 없거나 변호인이 변호한 사람 있으면 그 사람에서 진행 할 수 없을 때) 변호하고 true반환, 변호 못하면 false반환하도록 했다.
뭔가 부실한 로직임을 인정하지만 어떻게 고치면 가능할 것 같다는 생각이 아직도 든다.
이에 가장 처음 생각했던 한붓그리기 -> union-find방법을 사용했다. 어떤 사이클이든 완전 길이 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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/**
* Author: nowalex322, Kim HyeonJae
*/
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader br;
static BufferedWriter bw;
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
static int N, M;
static ArrayList<Integer>[] lawyer; // a->b 변호 관계
static ArrayList<Integer>[] doubleRelationship; // 양방향관계
static boolean[] isDefended; // 변호받았는지 여부
static boolean flag;
static int[] p;
public static void main(String[] args) throws Exception {
new Main().solution();
}
public void solution() throws Exception {
// br = new BufferedReader(new InputStreamReader(System.in));
br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
lawyer = new ArrayList[N + 1];
doubleRelationship = new ArrayList[N+1];
for (int i = 1; i <= N; i++) {
lawyer[i] = new ArrayList<>();
doubleRelationship[i] = new ArrayList<>();
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
lawyer[a].add(b);
}
isDefended = new boolean[N + 1];
p = new int[N+1];
for(int i=1; i<=N; i++) {
p[i] = i;
}
for(int i=1; i<=N; i++) { // 나
for(int l : lawyer[i]) { // 변호사
if(lawyer[l].contains(i)) {
// 서로 포함하므로
doubleRelationship[i].add(l);
}
else {
isDefended[l] =true;
}
}
}
for(int i=1; i<=N; i++) {
if(isDefended[i] || p[i] != i) continue;
flag = false;
dfs(i, i);
if(!flag) {
System.out.println("NO");
return;
}
}
System.out.println("YES");
bw.flush();
bw.close();
br.close();
}
private void dfs(int prev, int curr) {
for(int next : doubleRelationship[curr]) {
if(next == prev) continue;
if(isDefended[next]) {
flag = true;
}
if(!union(curr, next)) {
flag = true;
continue;
}
dfs(curr, next);
}
}
private boolean union(int x, int y) {
if(find(y) == find(x)) return false;
p[find(y)] = find(x);
return true;
}
private int find(int x) {
if(p[x] != x) return p[x] = find(p[x]);
return x;
}
}
This post is licensed under
CC BY 4.0
by the author.