구름톤 챌린지 4주 차 학습 일기 (Day16 ~ 18)
🧩 문제 16. 연합
> 배운 점
• 그래프 탐색 ⇨ BFS
• 인접 행렬 활용
> 필요 변수 및 자료구조
- int[][] graph ⇨ 인접 행렬
- boolean[] visited / int[] visited ⇨ 섬 방문 여부 확인 & 연합 여부 확인
- Queue<Integer> ⇨ BFS 수행용
> 느낀 점
- 연합 개수 = BFS 수행 횟수
- 나는 boolean[] visited로 풀었는데,
int[] visited로 해서 while문 안에 현재 방문한 노드를 연합 번호에 할당하는 코드인 visited[now] = cnt; 를 넣어서 풀 수도 있다!
> 헷갈렸던 점
- while문 안에 들어가는 if문에서 간선의 존재 여부를 확인할 때,
graph[now][next]와 graph[next][now]로 양방향 모두 확인해줘야한다..!!
> 정답 코드
|
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
|
import java.io.*;
import java.util.*;
class Main {
static int N, M, cnt;
static int[][] graph; // 인접 행렬
static boolean[] visited; // 섬 방문 여부 확인 & 연합 여부 확인
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
graph = new int[N + 1][N + 1];
while(M --> 0) {
st = new StringTokenizer(br.readLine(), " ");
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
graph[a][b] = 1; // 단방향
}
visited = new boolean[N + 1];
for(int i = 1 ; i <= N ; i++) {
if(!visited[i]) {
bfs(i);
cnt++;
}
}
System.out.println(cnt);
}
private static void bfs(int num) {
Queue<Integer> queue = new LinkedList<>();
queue.add(num);
visited[num] = true;
while(!queue.isEmpty()) {
int now = queue.poll();
for(int next = 1 ; next <= N ; next++) {
if(graph[now][next] == 1 && graph[next][now] == 1 && !visited[next]) {
queue.add(next);
visited[next] = true;
}
}
}
}
}
|
cs |
🧩 문제 17. 통신망 분석
> 배운 점
• 컴포넌트 : 그래프 내에서 서로 연결된 정점들의 집합
> 필요 변수 · 자료구조
• Com(List<Integer> list, double val) ⇨ 객체 (찾아낸 컴포넌트 리스트, 밀도)
• List<Integer> result ⇨ 정답 저장 리스트
• Set<Integer> component ⇨ 도달한 컴퓨터들을 오름차순 집합으로 저장할 집합
> 느낀 점
• 클래스에 List도 인자로 가질 수 있다!
• 함수 리턴형을 객체로 받을 수도 있다!
• 필요한 변수/자료구조가 어떤 것이 있는지 초장에 고민을 진득하게 하는 시간이 필요한 것 같다.
> 헷갈렸던 점
• 도달한 컴퓨터들을 저장할 목록을 만들자
> 풀이
🔍 찾아야 할 것
1. 컴포넌트에 속한 컴퓨터 수
2. 컴포넌트에 속한 통신 회선 수
3. 컴포넌트에서 가장 작은 컴퓨터 번호
|
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
import java.util.*;
import java.io.*;
class Com {
List<Integer> list; // 찾아낸 컴포넌트
double val; // 밀도
public Com(List<Integer> list, double val) {
this.list = list;
this.val = val;
}
}
public class Main {
static int N, M;
static List<Integer>[] A;
static boolean[] visited;
static List<Integer> result; // 🔔 정답 저장 리스트
static double density = 0;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
A = new ArrayList[N + 1];
for(int i = 1 ; i <= N ; i++) {
A[i] = new ArrayList<>();
}
visited = new boolean[N + 1];
while(M --> 0) {
st = new StringTokenizer(br.readLine(), " ");
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
A[a].add(b);
A[b].add(a);
}
result = new ArrayList<>(); // 정답 저장 리스트
for(int i = 1 ; i <= N ; i++) {
if(!visited[i]) {
Com com = bfs(i);
List<Integer> tmp = com.list;
double tmpDensity = com.val;
if(Math.abs(tmpDensity - density) < 1e-8) { // [밀도가 같은 경우]
if(result.size() > tmp.size()) { // 2번 조건) 현재 컴포넌트 배열이 더 크면, 컴퓨터 수가 가장 작은 컴포넌트 출력 (=result 값 확인)
result = tmp;
density = tmpDensity;
}
else if(result.size() == tmp.size()) { // 3번 조건) 배열 크기가 같으면, 더 작은 컴퓨터 번호 갖는 컴포넌트 출력 (=첫 번째 값 비교)
if(tmp.get(0) < result.get(0)) {
result = tmp;
density = tmpDensity;
}
}
}
else if(tmpDensity > density) { // [밀도가 다른 경우, 가장 밀도가 높은 컴포넌트 출력]
result = tmp;
density = tmpDensity;
}
}
}
for(int r : result) {
sb.append(r).append(" ");
}
System.out.println(sb);
}
private static Com bfs(int num) {
Queue<Integer> queue = new LinkedList<>();
queue.add(num);
Set<Integer> component = new TreeSet<>(); // 📍 도달한 컴퓨터들을 오름차순 집합으로 저장 (TreeSet : 객체 오름차순 정렬)
while(!queue.isEmpty()) {
int now = queue.poll();
if(visited[now]) {
continue;
}
visited[now] = true;
component.add(now);
for(int next : A[now]) {
if(!visited[next]) {
queue.add(next);
}
}
}
/*** 🔔 내부 통선 회신 개수 확인 ***/
int edge = 0; // 간선 수 저장
// 컴포넌트에 속한 모든 컴퓨터에 대해 순회
for(int i : component) {
for(int to : A[i]) {
if(component.contains(to)) { // contains 활용하기 위해 Set 쓰는 것!
edge++;
}
}
}
List<Integer> sortedList = new ArrayList<>(component);
//Collections.sort(sortedList);
return new Com(sortedList, (double) edge / component.size()); // "가장 밀도가 높은 컴포넌트" : 컴포넌트에 포함된 통신 회선 개수 / 컴퓨터 수
}
}
|
cs |
🧩 문제 18. 중첩 점
> 배운 점
• DP - 3차원 매트릭스!
> 필요 변수 및 자료구조
• long[][][] dp = new int[2][][]; ⇨ 선 긋기를 중첩 기록해 모두 관리할 수 있는 DP 변수
└ dp[0] ⇨ 한 좌표에서 세로 선 개수만 기록
└ dp[1] ⇨ 한 좌표에서 가로 선 개수만 기록
• long spotCnt : 중첩 점 개수
• [선 개수, 방향]을 갖고 있는 데이터 (객체/배열)가 필요하다!
• D / U (상하) : 가로 선을 관리하는 dp[1]에서 추출하며, dp[1]의 값을 갱신한다.
• R / L (좌우) : 세로 선을 관리하는 dp[0]에서 추출하며, dp[0]의 값을 갱신한다.
> 느낀 점
3차원 매트릭스 dp배열. 며칠 전에 문제로 풀 때 이 생각을 우째하지 싶었는데 이 문제에서 또 사용되었다
여기서 상하좌우 방향을 만날 때마다 각자의 조건문에 맞춰 반복문을 매번 수행하고,
중첩 점 개수를 갱신하고, dp를 갱신해주면 되는 것이었다..
정답 코드 보니 그리 어렵지 않음,,,,ㅠ