채우다

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15B1cKAKwCFAYD& 

• 알고리즘[풀이방법]

인접리스트를 활용한 BFS방법으로 풀었다. 큐에는 단순 숫자를 넣어 해당 숫자에 대한 접근 여부를 확인하여, 접근하지 않았을 경우 큐에 넣고 넘어간다. 큐가 비어있지 않을 경우, 사이즈를 확인하여, 해당 노드들이 각각 손을 뻗치는 순간을 한 턴으로 생각하였다. 매 턴마다 ANSWER변수를 0으로 초기화해주고, 그 턴에서 가장 큰 값을 저장한다. 마지막 턴에서 가장 큰 값을 출력하였다.

단순하게 큐대신 PQ에 넣어서 마지막에 나오는 값을 출력하면 어떨까 생각해보았는데, 이러면 무조건 나올수 있는 가장 큰 값이 마지막에 출력되게 되어 자꾸 100을 답으로 내뱉었다... 일반적인 큐로 하니 잘 돌아갔당

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public classSWEA1238_Contact {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer sb = new StringBuffer();
		for (int tc = 1; tc < 11; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			int S = Integer.parseInt(st.nextToken());
			ArrayList<Integer>[] list = new ArrayList[101];
			boolean[] visited = new boolean[101];
            //I에서 갈수 있는 노드를 모두 LIST[I]에 넣는다.
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < 101; i++) {
				list[i] = new ArrayList<>();
			}

			//FROM,TO를 합쳐서 N개이기 때문에 N/2만큼의 크기만 있으면 된다.
			for (int i = 0; i < N / 2; i++) {
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());
				if (!list[from].contains(to)) {
					list[from].add(to);
				}
			}

			Queue<Integer> q = new ArrayDeque<>();
			q.add(S);
			visited[S] = true;
			int max = Integer.MIN_VALUE;
			while (!q.isEmpty()) {
				int answer = 0;
				int size = q.size();
                //이번 턴에서 가장 큰 값을 ANSWER에 저장. 저장된 ANSWER를 MAX로 보낸다.
                //MAX는 매턴마다 덮어쓰여진다.
				for (int j = 0; j < size; j++) {
					int tmp = q.poll();
					answer = Math.max(tmp, answer);
					max = answer;
                    //이번 큐에서 갈 수 있는 노드중 방문하지 않았던 노드를 큐에 저장
					for (int i : list[tmp]) {
						if (!visited[i]) {
							q.add(i);
							visited[i] = true;
						}
					}
				}
			}
			sb.append("#").append(tc).append(" ").append(max).append("\n");
		}
		System.out.println(sb);
	}// main
}// class