문제 링크
1. 아이디어
컴퓨터를 노드, 연결 정보를 간선으로 간주한 그래프에서 1번 노드와 직간접적으로 연결된 다른 노드의 수를 구하는 문제로 생각할 수 있다. BFS 또는 DFS를 활용해서 방문한 노드의 수를 카운팅하면 해결할 수 있다. 노드의 수가 크지 않아서 인접 행렬을 활용해서 구현했다.
2. 복잡도
| 접근 | 시간 | 공간 |
|---|
| BFS | $O(N^2 + E)$ | $O(N^2)$ |
| DFS | $O(N^2 + E)$ | $O(N^2)$ |
($N$ = 입력값 n, $E$ = 입력값 m)
3. 코드
풀이 1: BFS [Java][C++]
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
| import java.io.*;
import java.util.*;
public class Main {
static int n;
static boolean[][] adj;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
adj = new boolean[1 + n][1 + n];
int m = Integer.parseInt(br.readLine());
while (m-- > 0) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
adj[u][v] = adj[v][u] = true;
}
System.out.println(bfs());
}
static int bfs() {
Queue<Integer> q = new ArrayDeque<>();
q.offer(1);
boolean[] vis = new boolean[1 + n];
vis[1] = true;
int cnt = 0;
while (!q.isEmpty()) {
int cur = q.poll();
for (int nxt = 1; nxt <= n; nxt++) {
if (!adj[cur][nxt] || vis[nxt]) continue;
q.offer(nxt);
vis[nxt] = true;
cnt++;
}
}
return cnt;
}
}
|
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
| #include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1 + 100;
int n;
bool adj[MAX_N][MAX_N];
bool vis[MAX_N];
int bfs() {
queue<int> q;
q.push(1);
vis[1] = true;
int cnt = 0;
while (!q.empty()) {
int cur = q.front();
q.pop();
for (int nxt = 1; nxt <= n; nxt++) {
if (!adj[cur][nxt] || vis[nxt]) continue;
q.push(nxt);
vis[nxt] = true;
cnt++;
}
}
return cnt;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int m;
cin >> n >> m;
while (m--) {
int u, v;
cin >> u >> v;
adj[u][v] = adj[v][u] = true;
}
cout << bfs();
}
|
풀이 2: DFS [Java][C++]
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
| import java.io.*;
import java.util.*;
public class Main {
static int n;
static boolean[][] adj;
static boolean[] vis;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
adj = new boolean[1 + n][1 + n];
vis = new boolean[1 + n];
int m = Integer.parseInt(br.readLine());
while (m-- > 0) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
adj[u][v] = adj[v][u] = true;
}
System.out.println(dfs(1) - 1);
}
static int dfs(int cur) {
vis[cur] = true;
int cnt = 1;
for (int nxt = 1; nxt <= n; nxt++) {
if (!adj[cur][nxt] || vis[nxt]) continue;
cnt += dfs(nxt);
}
return cnt;
}
}
|
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
| #include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1 + 100;
int n;
bool adj[MAX_N][MAX_N];
bool vis[MAX_N];
int dfs(int cur) {
vis[cur] = true;
int cnt = 1;
for (int nxt = 1; nxt <= n; nxt++) {
if (!adj[cur][nxt] || vis[nxt]) continue;
cnt += dfs(nxt);
}
return cnt;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int m;
cin >> n >> m;
while (m--) {
int u, v;
cin >> u >> v;
adj[u][v] = adj[v][u] = true;
}
cout << dfs(1) - 1;
}
|