[Java] SWEA 1238번 Contact

SW Expert Academy

---

풀이

문제에서 요구한 연락이 퍼지는 속도는 일정하다는 규칙이 있기에 bfs를 사용하여 해결했습니다.

간선을 입력받을 때에는 ArrayList를 사용하여 동적으로 할당받을 수 있게 했습니다.

또한, visit를 이용하여 각 정점마다의 연락받은 순번을 저장하여 문제에서 요구한 정답을 찾을 수 있게 했습니다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution {
	public static int len, start, answer;
	public static int[] visit;
	public static List<Integer>[] edge;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder("");
		StringTokenizer st;
		
		for (int tc = 1; tc <= 10; ++tc) {
			st = new StringTokenizer(br.readLine(), " ");
			
			len = Integer.parseInt(st.nextToken());
			start = Integer.parseInt(st.nextToken());
			
			visit = new int[101];
			edge = new ArrayList[101];
			
			answer = Integer.MIN_VALUE;
			
			for (int i = 1; i <= 100; ++i) {
				edge[i] = new ArrayList<Integer>();
			}
			
			st = new StringTokenizer(br.readLine(), " ");
			for (int i = 0; i < len / 2; ++i) {
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());
				
				edge[from].add(to);
			}
			
			visit[start] = 1;
			go();
			
			sb.append("#").append(tc).append(" ").append(answer).append("\n");
		}
		
		System.out.println(sb);
	}
	
	public static class Info {
		int vertex;
		int cnt;
		
		public Info(int vertex, int cnt) {
			this.vertex = vertex;
			this.cnt = cnt;
		}
	}
	
	public static void go() {
		Queue<Integer> q = new LinkedList<Integer>();
		q.offer(start);
		int maxCnt = Integer.MIN_VALUE;
		
		while (!q.isEmpty()) {
			int cur = q.poll();
			
			for (int i = 0; i < edge[cur].size(); ++i) {
				int v = edge[cur].get(i);
				
				if (visit[v] != 0) {
					continue;
				}
				
				visit[v] = visit[cur] + 1;
				q.offer(v);
			}
			
			// bfs이므로 계속 갱신하다보면 마지막에 갱신된는 값이 최대 값이된다.
			maxCnt = visit[cur];
		}
		
		for (int i = 1; i < 101; ++i) {
			if (maxCnt != visit[i]) {
				continue;
			}
			
			answer = (answer < i) ? i : answer;
		}
	}
}

---

pyo7410/Algorithm