๋ฌธ์
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/1389
- ์ผ๋น ๋ฒ ์ด์ปจ์ 6๋จ๊ณ ๋ฒ์น์ ์ํ๋ฉด ์ง๊ตฌ์ ์๋ ๋ชจ๋ ์ฌ๋๋ค์ ์ต๋ 6๋จ๊ณ ์ด๋ด์์ ์๋ก ์๋ ์ฌ๋์ผ๋ก ์ฐ๊ฒฐ๋ ์ ์๋ค. ์ผ๋น ๋ฒ ์ด์ปจ ๊ฒ์์ ์์์ ๋ ์ฌ๋์ด ์ต์ ๋ช ๋จ๊ณ ๋ง์ ์ด์ด์ง ์ ์๋์ง ๊ณ์ฐํ๋ ๊ฒ์์ด๋ค.
- ์ผ๋น ๋ฒ ์ด์ปจ์ ๋ฏธ๊ตญ ํ๋ฆฌ์ฐ๋ ์ํ๋ฐฐ์ฐ๋ค ๋ผ๋ฆฌ ์ผ๋น ๋ฒ ์ด์ปจ ๊ฒ์์ ํ์๋ ๋์ค๋ ๋จ๊ณ์ ์ด ํฉ์ด ๊ฐ์ฅ ์ ์ ์ฌ๋์ด๋ผ๊ณ ํ๋ค.
- ์ค๋์ Baekjoon Online Judge์ ์ ์ ์ค์์ ์ผ๋น ๋ฒ ์ด์ปจ์ ์๊ฐ ๊ฐ์ฅ ์์ ์ฌ๋์ ์ฐพ์ผ๋ ค๊ณ ํ๋ค. ์ผ๋น ๋ฒ ์ด์ปจ ์๋ ๋ชจ๋ ์ฌ๋๊ณผ ์ผ๋น ๋ฒ ์ด์ปจ ๊ฒ์์ ํ์ ๋, ๋์ค๋ ๋จ๊ณ์ ํฉ์ด๋ค.
- ์๋ฅผ ๋ค์ด, BOJ์ ์ ์ ๊ฐ 5๋ช ์ด๊ณ , 1๊ณผ 3, 1๊ณผ 4, 2์ 3, 3๊ณผ 4, 4์ 5๊ฐ ์น๊ตฌ์ธ ๊ฒฝ์ฐ๋ฅผ ์๊ฐํด๋ณด์.
- 1์ 2๊น์ง 3์ ํตํด 2๋จ๊ณ ๋ง์, 3๊น์ง 1๋จ๊ณ, 4๊น์ง 1๋จ๊ณ, 5๊น์ง 4๋ฅผ ํตํด์ 2๋จ๊ณ ๋ง์ ์ ์ ์๋ค. ๋ฐ๋ผ์, ์ผ๋น ๋ฒ ์ด์ปจ์ ์๋ 2+1+1+2 = 6์ด๋ค.
- 2๋ 1๊น์ง 3์ ํตํด์ 2๋จ๊ณ ๋ง์, 3๊น์ง 1๋จ๊ณ ๋ง์, 4๊น์ง 3์ ํตํด์ 2๋จ๊ณ ๋ง์, 5๊น์ง 3๊ณผ 4๋ฅผ ํตํด์ 3๋จ๊ณ ๋ง์ ์ ์ ์๋ค. ๋ฐ๋ผ์, ์ผ๋น ๋ฒ ์ด์ปจ์ ์๋ 2+1+2+3 = 8์ด๋ค.
- 3์ 1๊น์ง 1๋จ๊ณ, 2๊น์ง 1๋จ๊ณ, 4๊น์ง 1๋จ๊ณ, 5๊น์ง 4๋ฅผ ํตํด 2๋จ๊ณ ๋ง์ ์ ์ ์๋ค. ๋ฐ๋ผ์, ์ผ๋น ๋ฒ ์ด์ปจ์ ์๋ 1+1+1+2 = 5์ด๋ค.
- 4๋ 1๊น์ง 1๋จ๊ณ, 2๊น์ง 3์ ํตํด 2๋จ๊ณ, 3๊น์ง 1๋จ๊ณ, 5๊น์ง 1๋จ๊ณ ๋ง์ ์ ์ ์๋ค. 4์ ์ผ๋น ๋ฒ ์ด์ปจ์ ์๋ 1+2+1+1 = 5๊ฐ ๋๋ค.
- ๋ง์ง๋ง์ผ๋ก 5๋ 1๊น์ง 4๋ฅผ ํตํด 2๋จ๊ณ, 2๊น์ง 4์ 3์ ํตํด 3๋จ๊ณ, 3๊น์ง 4๋ฅผ ํตํด 2๋จ๊ณ, 4๊น์ง 1๋จ๊ณ ๋ง์ ์ ์ ์๋ค. 5์ ์ผ๋น ๋ฒ ์ด์ปจ์ ์๋ 2+3+2+1 = 8์ด๋ค.
- 5๋ช ์ ์ ์ ์ค์์ ์ผ๋น ๋ฒ ์ด์ปจ์ ์๊ฐ ๊ฐ์ฅ ์์ ์ฌ๋์ 3๊ณผ 4์ด๋ค.
- BOJ ์ ์ ์ ์์ ์น๊ตฌ ๊ด๊ณ๊ฐ ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ก์ ๋, ์ผ๋น ๋ฒ ์ด์ปจ์ ์๊ฐ ๊ฐ์ฅ ์์ ์ฌ๋์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
- ์ฒซ์งธ ์ค์ ์ ์ ์ ์ N (2 ≤ N ≤ 100)๊ณผ ์น๊ตฌ ๊ด๊ณ์ ์ M (1 ≤ M ≤ 5,000)์ด ์ฃผ์ด์ง๋ค.
- ๋์งธ ์ค๋ถํฐ M๊ฐ์ ์ค์๋ ์น๊ตฌ ๊ด๊ณ๊ฐ ์ฃผ์ด์ง๋ค. ์น๊ตฌ ๊ด๊ณ๋ A์ B๋ก ์ด๋ฃจ์ด์ ธ ์์ผ๋ฉฐ, A์ B๊ฐ ์น๊ตฌ๋ผ๋ ๋ป์ด๋ค. A์ B๊ฐ ์น๊ตฌ์ด๋ฉด, B์ A๋ ์น๊ตฌ์ด๋ฉฐ, A์ B๊ฐ ๊ฐ์ ๊ฒฝ์ฐ๋ ์๋ค. ์น๊ตฌ ๊ด๊ณ๋ ์ค๋ณต๋์ด ๋ค์ด์ฌ ์๋ ์์ผ๋ฉฐ, ์น๊ตฌ๊ฐ ํ ๋ช ๋ ์๋ ์ฌ๋์ ์๋ค. ๋, ๋ชจ๋ ์ฌ๋์ ์น๊ตฌ ๊ด๊ณ๋ก ์ฐ๊ฒฐ๋์ด์ ธ ์๋ค. ์ฌ๋์ ๋ฒํธ๋ 1๋ถํฐ N๊น์ง์ด๋ฉฐ, ๋ ์ฌ๋์ด ๊ฐ์ ๋ฒํธ๋ฅผ ๊ฐ๋ ๊ฒฝ์ฐ๋ ์๋ค.
์์ด๋์ด
- ์ต๋จ ๊ฑฐ๋ฆฌ์ด๊ธฐ ๋๋ฌธ์ BFS๋ฅผ ์ฌ์ฉํ์๋ค.
- ์ฐ์ ์ ๋ ฅ์ ๋ฐ์ผ๋ฉด์ ๊ฐ ๋ ธ๋๋ฅผ ์๋ฐฉํฅ์ผ๋ก ์ฐ๊ฒฐ์์ผ์ฃผ๊ณ for๋ฌธ์ ํตํด ๊ฐ ๋ ธ๋๋ฅผ ๋๋ฉด์ BFS๋ฅผ ๋๋ ค์ค๋ค.
- BFS๋ฅผ ๋๋ฆด๋, ๊ฐ ๋ ธ๋๋ง๋ค ๊ฑฐ๋ฆฌ๋ฅผ 0์ผ๋ก ์ด๊ธฐํํด์ฃผ๊ณ ์ด๊ธฐ ๋ ธ๋๋ฅผ Queue์ ๋ฃ์ด์ค๋ค, ๋ฐฉ๋ฌธ์ฒ๋ฆฌ๋ฅผ ํด์ฃผ๊ณ while๋ฌธ์ ๋๋ฆฐ๋ค.
- ๊ทธ๋ฆฌ๊ณ Queue์ ์๋ ๋ ธ๋๋ฅผ ๋นผ๊ณ ํด๋น ๋ ธ๋์ ์ฐ๊ฒฐ๋์ด ์๋ ๋ ธ๋ ์ค์ ๋ฐฉ๋ฌธ์ฒ๋ฆฌ๊ฐ ๋์ง ์์ ๋ ธ๋๊ฐ ์๋ค๋ฉด ๋ฐฉ๋ฌธ์ฒ๋ฆฌ๋ฅผ ํด์ฃผ๊ณ ํด๋น ๋ ธ๋์ ๊ฑฐ๋ฆฌ ๋ฐฐ์ด ๊ฐ์ ๊ธฐ์ค ๋ ธ๋ ๊ฑฐ๋ฆฌ + 1๊ฐ์ ์ ์ฅํ๋ค.
- ๊ทธ๋ฆฌ๊ณ ์ด ๊ฑฐ๋ฆฌ๋ฅผ ๋ํ๋ ๋ณ์์ ๋ํด์ฃผ๊ณ ํด๋น ๋ ธ๋๋ฅผ Queue์ ๋ฃ์ด์ค๋ค.
- ๊ทธ๋ฆฌ๊ณ ํ ๋ ธ๋๋ฅผ ๋ค ๋๋๋ง๋ค min๊ฐ๊ณผ ๋น๊ตํ์ฌ min๊ฐ์ ๊ฐฑ์ ์ํจ๋ค.
๊ฒช์ ์ํ์ฐฉ์ค
- ์ฒ์์ ์ต๋จ๊ฑฐ๋ฆฌ ๋ฌธ์ ์ด๊ธธ๋ BFS๋ก ํ๋ค๊ฐ ๊น์ด ์ฐ์ ํ์์ผ๋ก ํ์ด์ผ๋๋ ์ถ์ด์ DFS๋ก ํ์๋ค๊ฐ 50%์์ ํ๋ ธ๋ค..
- ๊ฒฐ๊ตญ ๋ค์ BFS๋ก ํ์ด์ ๋ง์ท๋ค...ใ ใ (์ต๋จ๊ฑฐ๋ฆฌ๋ BFS..! ๋ช ์ฌํ์...!)
์ฝ๋
import java.io.*;
import java.util.*;
public class BOJ1389 {
static int N;
static int M;
static ArrayList<Integer> friends[];
static boolean visited[];
static int result;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// ์ ์ ์ ์
N = Integer.parseInt(st.nextToken());
// ์น๊ตฌ ๊ด๊ณ์ ์
M = Integer.parseInt(st.nextToken());
// ์น๊ตฌ ๊ด๊ณ ์ฐ๊ฒฐ
friends = new ArrayList[N + 1];
// ๋
ธ๋ ๋ฐฉ๋ฌธ ์ฌ๋ถ
visited = new boolean[N + 1];
// ๊ฐ ๋
ธ๋ ์ฐ๊ฒฐ ํ์ ์ด ๋ํ ๋ณ์
result = 0;
// ํด๋น ๋ฐฐ์ด์ ArrayList๋ก ์ด๊ธฐํ
for(int i = 0; i <= N; i++){
friends[i] = new ArrayList<>();
}
for(int i = 0; i < M; i++){
StringTokenizer st2 = new StringTokenizer(br.readLine());
// ๋
ธ๋
int a = Integer.parseInt(st2.nextToken());
int b = Integer.parseInt(st2.nextToken());
// ์๋ก์ ๋
ธ๋์ ๋
ธ๋๋ฅผ ์ฐ๊ฒฐ
friends[a].add(b);
friends[b].add(a);
}
// ์ต์๊ฐ์ ๊ณ์ฐํ ๋ณ์
int min = Integer.MAX_VALUE;
// ์ ๋ต ์ ์
int user = 0;
// ๊ธฐ์ค ๋
ธ๋๊ฐ ์๊ธฐ ๋
ธ๋๋ง๊ณ ๋ค๋ฅธ ๋
ธ๋๋ฅผ ๋ฐฉ๋ฌธํ ๋๋ง๋ค
// BFS๋ฅผ ๋๋ ค์ ํ์๋ฅผ ์นด์ดํธ
for(int i = 1; i <= N; i++){
// ๋ฐฉ๋ฌธ ์ฌ๋ถ ์ด๊ธฐํ
visited = new boolean[N + 1];
// ๊ฐ ๋
ธ๋๋ง๋ค BFS๋ฅผ ๋๋ฆผ
BFS(i);
// min๋ณด๋ค ๊ฒฐ๊ณผ๊ฐ์ด ๋ ์์ผ๋ฉด min ๊ฐฑ์
if(min > result){
min = result;
user = i;
}
// BFS ๋๋ฆฐ ๊ฒฐ๊ณผ๊ฐ ์ด๊ธฐํ
result = 0;
}
System.out.println(user);
}
public static void BFS(int x){
Queue<Integer> q = new LinkedList<>();
// ๊ฑฐ๋ฆฌ๋ฅผ ์ ์ฅํ ๋ฐฐ์ด
int distance[] = new int[N + 1];
q.offer(x);
// ๋ฐฉ๋ฌธ ์ฒ๋ฆฌ
visited[x] = true;
// Queue๊ฐ ๋น๋๊น์ง ๋ฐ๋ณต
while(!q.isEmpty()){
int u = q.poll();
// ๊ธฐ์ค ์ ์ ์ ์ฐ๊ฒฐ๋์ด์๋ ์ ์ ๋ค์ ๊ธฐ์ค์ผ๋ก
for(int i : friends[u]){
if(!visited[i]){
// ๋ง์ฝ ํด๋น ์ ์ ๋ฅผ ์์ง ๋ฐฉ๋ฌธํ์ง ์์๋ค๋ฉด
// ๋ฐฉ๋ฌธ ์ฒ๋ฆฌ ํ, ๊ธฐ์ค ์ ์ ์ ๊ฑฐ๋ฆฌ + 1๋งํผ ๋ฐฐ์ด์ ์ ์ฅ
visited[i] = true;
distance[i] = distance[u] + 1;
// ๊ทธ๋ฆฌ๊ณ ๋ชจ๋ ์ ์ ์ ๊ฑฐ๋ฆฌ๋ฅผ ์ ์ฅํ๋ ๋ฐฐ์ด์ ํด๋น ์ ์ ๊ฑฐ๋ฆฌ๋ฅผ
// ์ ์ฅํ๊ณ Queue์ ๋ฃ์
result = result + distance[i];
q.offer(i);
}
}
}
}
}
'์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Java] BOJ 1931 ํ์์ค ๋ฐฐ์ (0) | 2024.08.21 |
---|---|
[Java] BOJ 1697 ์จ๋ฐ๊ผญ์ง (0) | 2024.08.20 |
[Java] BOJ 1074 Z (0) | 2024.08.18 |
[Java] BOJ 30804 ๊ณผ์ผ ํํ๋ฃจ (2) | 2024.08.17 |
[Java] BOJ 21736 ํ๋ด๊ธฐ๋ ์น๊ตฌ๊ฐ ํ์ํด (0) | 2024.08.16 |