[SWEA JAVA] 1238. [S/W 문제해결 기본] 10일차 - Contact

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

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 Main {
	public static int T, V = 100, K, N;
	public static int[] visited;
	public static List<Integer>[] graph;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		T = 10;
		for (int tc = 1; tc <= T; tc++) {
			// 1. 입력값 받기
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			graph = new ArrayList[V + 1];
			visited = new int[V + 1];
			for (int i = 1; i < V + 1; i++) {
				graph[i] = new ArrayList<>();
			}

			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());
				graph[from].add(to);
			}

			Queue<Integer> q = new LinkedList<>();

			q.offer(K);
			visited[K] = 1;

			int max = 0;
			while (!q.isEmpty()) {
				int size = q.size();
				max = 0;
				for (int i = 0; i < size; i++) {
					int cur = q.poll();
					if(cur > max) {
						max = cur;
					}
					for (int d : graph[cur]) {
						if (visited[d] == 1)
							continue;
						visited[d] = 1;
						q.offer(d);

					}
				}
			}

			System.out.println("#" + tc + " " + max);

		}
	}
}

풀이 사항
풀이 일자: 2024.08.28
풀이 시간: 60분 00초
채점 결과: 정답
예상 문제 유형: 그래프 탐색 BFS

 

풀이 방법

1. 그래프의 간선들을 인접 리스트로 받아오고 최대값인 100만큼 visited선언해준다.

 

2. 큐에 시작값을 넣고 큐가 비워질때까지 반복하는 while문안에서 현재 들어있는 큐에 사이즈만큼만 반복하고 넘어간다. 이런식으로 하면 한 depth만큼 작업을 할 수 있는데 그중에서 같은 깊이에서 최대값을 계속 계산해주었다.

 

3. 마지막까지 저장되어있는 층의 최대값을 출력해준다.

 

간단하다고 생각했는데 기본기가 부족해서 size를 먼저 만들어주고 하는것때문에 오류가 발생했다.