๐ ํ๋ก๊ทธ๋๋จธ์ค / Graph / Level 2 / ๊ฐ์ฅ ๋จผ ๋ ธ๋
๐ ๋ฌธ์
ํ๋ก๊ทธ๋๋จธ์ค
์ฝ๋ ์ค์ฌ์ ๊ฐ๋ฐ์ ์ฑ์ฉ. ์คํ ๊ธฐ๋ฐ์ ํฌ์ง์ ๋งค์นญ. ํ๋ก๊ทธ๋๋จธ์ค์ ๊ฐ๋ฐ์ ๋ง์ถคํ ํ๋กํ์ ๋ฑ๋กํ๊ณ , ๋์ ๊ธฐ์ ๊ถํฉ์ด ์ ๋ง๋ ๊ธฐ์ ๋ค์ ๋งค์นญ ๋ฐ์ผ์ธ์.
programmers.co.kr
๐ซ ์ ํ ์ฌํญ
- ๋ ธ๋์ ๊ฐ์ n์ 2 ์ด์ 20,000 ์ดํ์ ๋๋ค.
- ๊ฐ์ ์ ์๋ฐฉํฅ์ด๋ฉฐ ์ด 1๊ฐ ์ด์ 50,000๊ฐ ์ดํ์ ๊ฐ์ ์ด ์์ต๋๋ค.
- vertex ๋ฐฐ์ด ๊ฐ ํ [a, b]๋ a๋ฒ ๋ ธ๋์ b๋ฒ ๋ ธ๋ ์ฌ์ด์ ๊ฐ์ ์ด ์๋ค๋ ์๋ฏธ์ ๋๋ค.
๐ ์ ์ถ๋ ฅ ์
| n | vertex | return |
| 6 | [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] | 3 |
๐ค ํ์ด ๋ฐฉ๋ฒ

1๏ธโฃ ๊ทธ๋ํ ๊ตฌํ
โก๏ธ ๊ทธ๋ํ ๊ตฌํ ๋ฐฉ๋ฒ์๋ ํฌ๊ฒ (1) ์ธ์ ๋ฐฐ์ด ์ฌ์ฉ ๊ณผ (2) ์ธ์ ๋ฆฌ์คํธ ์ฌ์ฉ์ด ์๋๋ฐ ๊ณต๊ฐ ํจ์จ์ฑ์ ์ํด ๋ ์ค ์ธ์ ๋ฆฌ์คํธ ์ฌ์ฉ์ ์ ํํ๋ค. ๋ํ ๋ ธ๋์ ๊ฐ์ n ์ด ๋ฏธ๋ฆฌ ์ฃผ์ด์ก๊ธฐ ๋๋ฌธ์ ์ธ์ ๋ฆฌ์คํธ ๊ตฌํ์ ์์ด ๋ฐฐ์ด + ๋ฆฌ์คํธ ์กฐํฉ์ ์ฌ์ฉํ์๋ค.
โ ๊ทธ๋ํ ์ ์ธ ๋ฐ ์ด๊ธฐํ
// ๋
ธ๋๋ฅผ ๋ํ๋ด๋ ๋ฐฐ์ด ์์ฑ
ArrayList<Integer>[] list = new ArrayList[n+1];
// ์ธ์ ๋
ธ๋๋ฅผ ๋ด๊ธฐ์ํ ๋ฆฌ์คํธ ์์ฑ
for (int i=0; i<=n; i++) list[i] = new ArrayList<>();
// input edge 2์ฐจ์ ๋ฐฐ์ด์ ๊ฐ์ list ๋ก ๋ด๋ ๊ณผ์
for (int[] e : edge) {
list[e[0]].add(e[1]);
list[e[1]].add(e[0]);
}

2๏ธโฃ ์ธ์ ๋ ธ๋์ ์ต๋จ๊ฑฐ๋ฆฌ ํ์
โก๏ธ ๊ทธ๋ํ ํ์์ ๋ฐฉ๋ฒ์๋ ํฌ๊ฒ (1) DFS ์ (2) BFS ๊ฐ ์๋๋ฐ, "์ต๋จ๊ฑฐ๋ฆฌ" ๋ผ๋ ํค์๋๋ฅผ ๋ณด์๋ง์ BFS ๋ก ์ ๊ทผํด์ผ๊ฒ ๋ค๋ ์๊ฐ์ด ๋ค์๋ค.
โ ๊ทธ๋ํ์์์ BFS ํ์ ๊ณผ์
โก๏ธ ๊ทธ๋ํ์์ BFS ํ์ ๊ณผ์ ์ ์ฌ์ฉ๋๋ ์๋ฃ๊ตฌ์กฐ๋ (1) ํ (Queue) ์ ๋ฐฉ๋ฌธํ์ธ์ ์ํ (2) boolean ํ์ ์ visited ๋ฐฐ์ด ์ด๋ค. ์์ ๋ ธ๋๋ถํฐ ์ธ์ ํ ๋ ธ๋๋ค์ ์ฐจ๋ก๋๋ก Queue ์ ๋ด๋๋ค. ๋จ, ์ด๋ฏธ visited ๋ ๋ ธ๋๋ผ๋ฉด Queue ์ ๋ด์ง ์๊ณ ์ง๋๊ฐ๋ค.\
โ๏ธ ๊ทธ๋ํ ํ์ ์์
โ โก๏ธ โข โก๏ธ โก โก๏ธ โฅ โก๏ธ โฃ โก๏ธ โค
โก๏ธ ๋ ธ๋ โ ๋ก ๋ถํฐ ๊ฑฐ๋ฆฌ 1 ์ธ โก, โข ์ ๋จผ์ ํ์ ํ ๊ฑฐ๋ฆฌ 2 ์ธ โฃ, โค, โฅ ์ ํ์ํ๋ค.
/*
๋ชฉ์ : ์์๋
ธ๋๋ก๋ถํฐ ๋
ธ๋๋ค์ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ์ธก์
๋ณ์ : start โก๏ธ ํ์์ ์์ํ๋ ๋
ธ๋
*/
public static void BFS (int start) {
int tmp = 0; // Queue ์์ poll ํ ๊ฐ์ ๋ด๊ธฐ ์ํ ์ง์ญ ๋ณ์
visited[start] = true; // ์์ ๋
ธ๋๋ฅผ ๋ฐฉ๋ฌธ ์ฒ๋ฆฌ
q.add(start); // Queue ์ ์์ ๋
ธ๋๋ฅผ ๋ด์
while (q.size() != 0) {
tmp = q.poll();
for (int node : list[tmp]) { // ์ธ์ ํ ๋
ธ๋๋ค์ ํ์ธ
// ๊ฒฝ์ฐ (1) ์ด๋ฏธ ๋ฐฉ๋ฌธํ ๋
ธ๋ : continue
if (visited[node]) continue;
// ๊ฒฝ์ฐ (2) ๋ฐฉ๋ฌธ ์ ๋
ธ๋ : ๋ฐฉ๋ฌธ์ฒ๋ฆฌ ๋ฐ Queue ์ ๋ด์
visited[node] = true;
q.add(node);
// ์ต๋จ ๊ฑฐ๋ฆฌ : ์ธ์ ๋
ธ๋ ๊ฑฐ๋ฆฌ + 1
len[node] = len[tmp] + 1;
}
}
}

โก ์ต๋จ๊ฑฐ๋ฆฌ ์ค max ๊ฐ ํ์ธ ๋ฐ ๊ฐ์ ํ์ธ
โก๏ธ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ๋ด๊ธด ๋ณ์ len ์ Arrays.sort() ๋ฅผ ํตํด ์ค๋ฆ์ฐจ์ ์ ๋ ฌํ๊ณ , ๋ง์ง๋ง ๊ฐ์ max ๋ก ์ ํ๋ค. ๊ทธ ํ len ๋ฐฐ์ด์ ์ํ์ ํตํด max ๊ฐ๊ณผ ์ผ์นํ๋ ๋ณ์์ ๊ฐ์๋ฅผ ํ์ธํ๋ฉด ๊ณง answer ๊ฐ ๋๋ค.
// ์ต๋๊ฐ ํ์ธ
Arrays.sort(len);
int max = len[n];
// ๊ฐ์ ํ์ธ
for (int i=0; i<=n; i++) {
if (len[i] == max) answer++;
}
3๏ธโฃ ๊ฒฐ๊ณผ ํ์ธ
โก๏ธ ๋ชจ๋ ํ ์คํธ ์ผ์ด์ค์์ ํต๊ณผํ์๋ค.

๐ป ํ์ด ์ฝ๋
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;
import java.util.Arrays;
class Solution {
// ๊ทธ๋ํ ์์ฑ์ ์ํ ์ธ์ ๋ฆฌ์คํธ ์ ์ธ
public static ArrayList<Integer>[] list;
// BFS ์์ ๋ฐฉ๋ฌธ ํ์ธ์ ์ํ boolean ๋ฐฐ์ด ์ ์ธ
public static boolean[] visited;
// BFS ์์ ๋์ด ์ฐ์ ํ์์ ์ํ Queue ์ ์ธ
public static Queue<Integer> q;
// ๊ฐ์ฅ ๋ฉ๋ฆฌ ๋จ์ด์ง ๋
ธ๋๋ฅผ ํ์ธํ๊ธฐ ์ํ ArrayList ์ ์ธ
public static int[] len;
public int solution(int n, int[][] edge) {
// ์ด๊ธฐํ
int answer = 0;
visited = new boolean[n+1];
q = new LinkedList<>();
len = new int[n+1];
list = new ArrayList[n+1];
for (int i=0; i<=n; i++) list[i] = new ArrayList<>();
// edge 2์ฐจ์ ๋ฐฐ์ด์ ๊ฐ์ list ๋ก ๋ด๋ ๊ณผ์
for (int[] e : edge) {
list[e[0]].add(e[1]);
list[e[1]].add(e[0]);
}
// // ๊ทธ๋ํ ์ถ๋ ฅ
// for (int i = 1; i <= n; i++) {
// for(int j = 0 ; j < list[i].size();j++)
// System.out.print(list[i].get(j)+" ");
// System.out.println();
// }
BFS(1);
// // ๊น์ด ํ์ธ
// for (int d : len) {
// System.out.print(d + " ");
// }
// ์ต๋๊ฐ ํ์ธ
Arrays.sort(len);
int max = len[n];
// ๊ฐ์ ํ์ธ
for (int i=0; i<=n; i++) {
if (len[i] == max) answer++;
}
return answer;
}
public static void BFS (int start) {
int tmp = 0;
visited[start] = true;
q.add(start);
while (q.size() != 0) {
tmp = q.poll();
for (int node : list[tmp]) {
if (visited[node]) continue;
visited[node] = true;
q.add(node);
len[node] = len[tmp] + 1;
}
}
}
}
[level 3] Title: ๊ฐ์ฅ ๋จผ ๋ ธ๋, Time: 110.52 ms, Memory: 97.7 MB -BaekjoonHub · Young998904/Practice_Algorithm_Auto@684d868
Show file tree Showing 2 changed files with 127 additions and 0 deletions.
github.com