์ผ๋น ๋ฒ ์ด์ปจ์ 6๋จ๊ณ ๋ฒ์น์ ์ํ๋ฉด ์ง๊ตฌ์ ์๋ ๋ชจ๋ ์ฌ๋๋ค์ ์ต๋ 6๋จ๊ณ ์ด๋ด์์ ์๋ก ์๋ ์ฌ๋์ผ๋ก ์ฐ๊ฒฐ๋ ์ ์๋ค. ์ผ๋น ๋ฒ ์ด์ปจ ๊ฒ์์ ์์์ ๋ ์ฌ๋์ด ์ต์ ๋ช ๋จ๊ณ ๋ง์ ์ด์ด์ง ์ ์๋์ง ๊ณ์ฐํ๋ ๊ฒ์์ด๋ค.
์๋ฅผ ๋ค๋ฉด, ์ ํ ์๊ด์์ ๊ฒ ๊ฐ์ ์ธํ๋ํ๊ต์ ์ด๊ฐํธ์ ์๊ฐ๋ํ๊ต์ ๋ฏผ์ธํฌ๋ ๋ช ๋จ๊ณ๋ง์ ์ด์ด์ง ์ ์์๊น?
์ฒ๋ฏผํธ๋ ์ด๊ฐํธ์ ๊ฐ์ ํ๊ต์ ๋ค๋๋ ์ฌ์ด์ด๋ค. ์ฒ๋ฏผํธ์ ์ต๋ฐฑ์ค์ Baekjoon Online Judge๋ฅผ ํตํด ์๊ฒ ๋์๋ค. ์ต๋ฐฑ์ค๊ณผ ๊น์ ์์ ๊ฐ์ด Startlink๋ฅผ ์ฐฝ์ ํ๋ค. ๊น์ ์๊ณผ ๊น๋ํ์ ๊ฐ์ ํ๊ต ๋์๋ฆฌ ์์์ด๋ค. ๊น๋ํ๊ณผ ๋ฏผ์ธํฌ๋ ๊ฐ์ ํ๊ต์ ๋ค๋๋ ์ฌ์ด๋ก ์๋ก ์๊ณ ์๋ค. ์ฆ, ์ด๊ฐํธ-์ฒ๋ฏผํธ-์ต๋ฐฑ์ค-๊น์ ์-๊น๋ํ-๋ฏผ์ธํฌ ์ ๊ฐ์ด 5๋จ๊ณ๋ง ๊ฑฐ์น๋ฉด ๋๋ค.
์ผ๋น ๋ฒ ์ด์ปจ์ ๋ฏธ๊ตญ ํ๋ฆฌ์ฐ๋ ์ํ๋ฐฐ์ฐ๋ค ๋ผ๋ฆฌ ์ผ๋น ๋ฒ ์ด์ปจ ๊ฒ์์ ํ์๋ ๋์ค๋ ๋จ๊ณ์ ์ด ํฉ์ด ๊ฐ์ฅ ์ ์ ์ฌ๋์ด๋ผ๊ณ ํ๋ค.
์ค๋์ 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๊น์ง์ด๋ฉฐ, ๋ ์ฌ๋์ด ๊ฐ์ ๋ฒํธ๋ฅผ ๊ฐ๋ ๊ฒฝ์ฐ๋ ์๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ BOJ์ ์ ์ ์ค์์ ์ผ๋น ๋ฒ ์ด์ปจ์ ์๊ฐ ๊ฐ์ฅ ์์ ์ฌ๋์ ์ถ๋ ฅํ๋ค. ๊ทธ๋ฐ ์ฌ๋์ด ์ฌ๋ฌ ๋ช ์ผ ๊ฒฝ์ฐ์๋ ๋ฒํธ๊ฐ ๊ฐ์ฅ ์์ ์ฌ๋์ ์ถ๋ ฅํ๋ค.
๐ก ์น๊ตฌ๋ผ๋ฆฌ ์ฐ๊ฒฐ๋์ด ์๋ค๋ฉด ์ฐ๊ฒฐ๋ฆฌ์คํธ์ ๋ฃ์ด์ค
๐ก cnt๋ฅผ ์ฌ์ฉํ์ฌ ๋จ๊ณ๋ฅผ ์์๋ด๊ณ visited๋ฅผ ํตํด ๋ฐฉ๋ฌธ์ฌ๋ถ๋ฅผ ํ๋ณํจ
๐ก ์์ ์ฌ๋์ ๊ธฐ์ค์ผ๋ก ์ฐ๊ฒฐ๋ฆฌ์คํธ์ ์๋ ์ฌ๋๋ค์ queue์ ์ถ๊ฐํ๊ณ ๊ฐ ๋จ๊ณ๋ฅผ +1ํด์ค
๐ก ๊ฐ ์ฌ๋์ ๋ช
์๋งํผ ๊ธฐ์ค ์ฌ๋์ ๋ฌ๋ฆฌํ๋ฉฐ bfs๋ฅผ ํด์ฃผ๊ณ , ๊ทธ ๊ฒฐ๊ณผ๊ฐ ์ค ๊ฐ์ฅ ์์ ๊ฐ์ ์ธ๋ฑ์ค๋ฅผ ์ถ๋ ฅํจ
for(int i=0; i<m; i++) {
s = br.readLine().split(" ");
int v = Integer.parseInt(s[0]);
int w = Integer.parseInt(s[1]);
relation[v].add(w);
relation[w].add(v);
}
while(!q.isEmpty()) {
Person now = q.poll();
for(int connect : relation[now.vertex]) {
if(!visited[connect]) {
sum+=(now.cnt+1);
q.add(new Person(connect,now.cnt+1));
visited[connect] = true;
}
}
}
int min = Integer.MAX_VALUE;
int flag = -1;
for(int i=1; i<n+1; i++) {
int ret = bfs(i);
if(min > ret) {
min = ret;
flag = i;
}
Arrays.fill(visited, false);
}
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Queue;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Arrays;
public class Bruteforce_6 {
static ArrayList<Integer>[] relation;
static boolean[] visited;
static int n;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(" ");
n = Integer.parseInt(s[0]);
int m = Integer.parseInt(s[1]);
visited = new boolean[n+1];
relation = new ArrayList[n+1];
for(int i=1; i<n+1; i++)
relation[i] = new ArrayList<>();
for(int i=0; i<m; i++) {
s = br.readLine().split(" ");
int v = Integer.parseInt(s[0]);
int w = Integer.parseInt(s[1]);
relation[v].add(w);
relation[w].add(v);
}
int min = Integer.MAX_VALUE;
int flag = -1;
for(int i=1; i<n+1; i++) {
int ret = bfs(i);
if(min > ret) {
min = ret;
flag = i;
}
Arrays.fill(visited, false);
}
System.out.println(flag);
}
static int bfs(int start) {
Queue<Person> q = new LinkedList<>();
q.add(new Person(start,0));
visited[start] = true;
int sum = 0;
while(!q.isEmpty()) {
Person now = q.poll();
for(int connect : relation[now.vertex]) {
if(!visited[connect]) {
sum+=(now.cnt+1);
q.add(new Person(connect,now.cnt+1));
visited[connect] = true;
}
}
}
return sum;
}
static class Person{
int vertex;
int cnt;
Person(int vertex, int cnt){
this.vertex = vertex;
this.cnt = cnt;
}
}
}
์ฑ๊ณตโจ
list์ ๊ฐ๊ฐ ๋ฃ์ด์ฃผ๋ ๊ฑฐ๋ฅผ ๊น๋นกํ๋ค๐ฅ