[SWEA] Contact

Posted on | In |

문제 보러가기

제한사항

이외의 제한사항은 없다.

첫번째 생각

일반적인 BFS를 연습했다면, BFS의 응용으로 적당한 난이도의 문제로 BFS안에서 BFS 탐색을 한번 더 돌려주는 방식으로 문제를 해결하였따.

JAVA Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Solution {
	public static int[][] map;
	public static boolean[] visit;
	public static int N, M;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		for (int tc = 1; tc <= 10; tc++) {
			int N = sc.nextInt();
			int start = sc.nextInt();

			map = new int[101][101]; // 1번부터 쓰느거라 인덱스 +1 해놓기
			visit = new boolean[101];
			for (int i = 0; i<(N/2); i++) {
				int from = sc.nextInt();
				int to = sc.nextInt();
				map[from][to] = 1;
			}

			Queue<Integer> q = new LinkedList<>();
			Queue<Integer> q2 = new LinkedList<>();
			q.add(start);
			visit[start] = true;
			int max = -1;
			int max_s= 0;
			while (!q.isEmpty() || !q2.isEmpty()) {
				max = -1;
				while (!q2.isEmpty()) {
					int from2 = q2.poll();
					for (int to = 1; to < 101; to++) {
						if (map[from2][to] == 1) {
							if (!visit[to]) {
								visit[to] = true;
								q.add(to);
								max = max > to ? max : to;
								max_s = max;
							}
						}
					}
					
				}
				max = -1;
				while(!q.isEmpty()) {
					int from = q.poll();
					for (int to = 1; to < 101; to++) {
						if (map[from][to] == 1) {
							if (!visit[to]) {
								visit[to] = true;
								q2.add(to);
								max = max > to ? max : to;
								max_s = max;
							}
						}
					}
				}
			}
			
			if( max == -1 ) {
				System.out.println("#"+tc+" "+max_s);
			} else {
				System.out.println("#"+tc+" "+max);
			}
		}
	}
}