SWEA_D4_1238
๐ [D4_1238] Contact
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;
public class Solution{
static StringTokenizer st;
static int N;
static int[][] arr;
static int[] visited;
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
StringBuilder sb = new StringBuilder();
for(int tc=1; tc<=10; tc++){
sb.append("#").append(tc).append(" ");
// ๋ฐ์ดํฐ ๊ธธ์ด
N = sc.nextInt();
// ์์์
int first = sc.nextInt();
// ๊ฐ์ ์ ๋ณด ์ ์ฅ ๋ฐฐ์ด
arr = new int[101][101];
// ์ฐ๋ฝ ๋ฐ์ ์ ๋ฌด
visited = new int[101];
for(int i =0; i<N/2; i++){
// ๋ฐฉํฅ์ฑ์ด ์๋ค
arr[sc.nextInt()][sc.nextInt()] = 1;
}
bfs(first);
// ์ต๋๊ฐ ๊ตฌํ๊ธฐ
int maxCnt = Integer.MIN_VALUE;
int maxIdx = Integer.MIN_VALUE;
for(int i=1; i<101; i++){
// ๊ฐ์ง์น๊ธฐ
if(visited[i]==0){
continue;
}
// ์ ์ผ ๋ง์ cnt๊ตฌํ๊ธฐ
maxCnt = Math.max(visited[i], maxCnt);
if(maxCnt == visited[i]){
maxIdx = Math.max(maxIdx, i);
}
}
sb.append(maxIdx).append("\n");
}
System.out.println(sb);
}
public static void bfs(int start){
Queue<Integer> queue = new LinkedList<Integer>();
queue.offer(start);
visited[start] = 1;
while(!queue.isEmpty()){
int current = queue.poll();
for(int i=1; i<101; i++) {
if (visited[i]==0 && arr[current][i] != 0) {
queue.offer(i);
visited[i] = visited[current]+1;
}
}
}
}
}
๐ค ๋์ ์๊ฐ
์ผ๋ฐ์ ์ผ๋ก boolean์ผ๋ก bfs()์์ ๋ฐฉ๋ฌธ ์ ๋ฌด๋ฅผ ๊ตฌํ๋๋ฐ ์ด ๋ฌธ์ ์์๋ intํ ๋ฐฐ์ด๋ก ๋ช๋ฒ ๋ง์ ์ฐ๊ฒฐ์ด ๋์๋์ง ์ฒดํฌ๋ฅผ ํด์ฃผ์๋ค.
๊ทธ๋์ ๊ทธ ๊ฐ์ ์ด์ฉํด ๊ฐ์ ์ ๋ผ๋ฆฌ์์๋ ์ต๋๊ฐ์ ๊ตฌํด์ฃผ์๋ค.
Queue๋ฅผ ์ด์ฉํด์ bfs๋ฅผ ๊ตฌํํด์ฃผ๊ณ visited ๋ฐฐ์ด์ ๋๋ฉฐ ๊ฐ์ฅ ๋ค์ ์ฐ๋ฝ์ ๋ฐ์ ์ฌ๋ ์ค์ ๊ฐ์ฅ ํฐ ์๋ฅผ ๊ตฌํด์ฃผ์๋ค.
visited ๋ฐฐ์ด๋ก ์นด์ดํ
ํด์ค๋ค๋ฉด ์ด๋ ต์ง ์์ ๋ฌธ์ ์๋ค.
๋๋ static์ผ๋ก ๋ฐฐ์ด์ ์ ์ธ ํด๋๊ณ ์์์ ์ง์ญ์ผ๋ก ๋ค์ ์ ์ธ์ ํด์ ๊ฐ์ด ์ด์ํ ์ค๋ฅ๋ฅผ ๋นจ๋ฆฌ ์ฐพ์ง ๋ชปํด ๊ณ ์ํ์๋ฐ..ใ