[SW1238] Contact

 SW Expert Academy - Contact 

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15B1cKAKwCFAYD&categoryId=AV15B1cKAKwCFAYD&categoryType=CODE&problemTitle=contact&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1&&&&&&&&& 

SW Expert Academy

 

문제 입출력

300 42
42 68 35 1 70 25 79 59 63 65 6 46 82 28 62 92 96 43 28 37 92 5 3 54 93 83 22 17 19 96 48 27 72 39 70 13 68 100 36 95 4 12 23 34 74 65 42 12 54 69 48 45 63 58 38 60 24 42 30 79 17 36 91 43 89 7 41 43 65 49 47 6 91 30 71 51 7 2 94 49 30 24 85 55 57 41 67 77 32 9 45 40 27 24 38 39 19 83 30 42 34 16 40 59 5 31 78 7 74 87 22 46 25 73 71 30 78 74 98 13 87 91 62 37 56 68 56 75 32 53 51 51 42 25 67 31 8 92 8 38 58 88 54 84 46 10 10 59 22 89 23 47 7 31 14 69 1 92 63 56 11 60 25 38 49 84 96 42 3 51 92 37 75 21 97 22 49 100 69 85 82 35 54 100 19 39 1 89 28 68 29 94 49 84 8 22 11 18 14 15 10 17 36 52 1 50 20 57 99 4 25 9 45 10 90 3 96 86 94 44 24 88 15 4 49 1 59 19 81 97 99 82 90 99 10 58 73 23 39 93 39 80 91 58 59 92 16 89 57 12 3 35 73 56 29 47 63 87 76 34 70 43 45 17 82 99 23 52 22 100 58 77 93 90 76 13 1 11 4 70 62 89 2 90 56 24 3 86 83 86 89 27 18 58 33 33 70 55 22 90 
24 2
2 7 11 6 6 2 2 15 15 4 4 2 4 10 7 1 1 7 1 8 1 17 3 22
24 2
100 17 39 22 100 8 100 7 7 100 2 7 2 15 15 4 6 2 11 6 4 10 4 2

#1 96
#2 17
#3 17

 

문제 풀이

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;


public class Solution {
	static int ans, T = 10, N, K;
	static boolean[][] matrix;
	static boolean[] visit;
	static StringBuilder sb = new StringBuilder();

	static Queue<Integer> q = new ArrayDeque<>();
	static PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());


	public static void main(String[] args) throws Exception {
		//System.setIn(new FileInputStream("input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		for (int t = 1; t <= T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());

			// 초기화
			matrix = new boolean[101][101];
			visit = new boolean[101];
			ans = 0;
			q.clear();
			pq.clear();

			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N / 2; i++) {
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());
				matrix[from][to] = true;
			}

			// 탐색
			bfs(K);

			// 출력
			sb.append("#" + t + " " + ans + "\n");
		}

		System.out.println(sb.toString());

	} // end main


	private static void bfs(int v) {
		visit[v] = true;
		q.offer(v);

		while (!q.isEmpty()) {
			int size = q.size();
			pq.clear();

			for (int i = 0; i < size; i++) {
				int cur = q.poll();
				pq.offer(cur);

				for (int j = 1; j <= 100; j++) {
					if (!matrix[cur][j]) continue;
					if (visit[j]) continue;

					q.offer(j);
					visit[j] = true;
				}

			}

			if (!pq.isEmpty()) ans = pq.peek();

		}

	} // end bfs
}

• bfs depth 를 이용해서 간단히 풀 수 있는 문제입니다.
• 저는 PriorityQueue 를 이용해서 각 depth 마다의 첫번째 요소를 peek() 했습니다.
• 그렇게 하다보면 답인 제일 마지막 depth 의 peek() 도 담깁니다.
• depth 마다 사이즈를 돌아야 합니다.

 

 

 

 

 

 

 

 

 

# SWEA Contact java bfs # sw contact java # sw contact bfs

---