(Java/자바) - SWEA 1238번 :[S/W 문제해결 기본] 10일차 - Contact

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

SW Expert Academy

---

• 문제 : 

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

 

 

 

 

---

• 풀이 :

그래프 탐색 문제였습니다.

 

그래프를 탐색하는데 가장 높은 Depth를 가진 노드들 중 가장 큰 번호를 찾으면 됩니다.

 

BFS로 해결하였습니다.

 

1. ArrayList의 배열을 사용하여 그래프 생성

 

2. depth와 방문여부를 동시에 확인하기 위해 visited배열을 int 배열로 생성

 

3. bfs로 탐색하며 시작점을 depth = 1, 이후 depth + 1씩 한다.

 

4. 탐색이 종료된 후 가장 높은 Depth를 가진 노드들을 찾으며 가장 큰 노드의 번호를 기록한다.

 

 

 

---

• 소스코드 : 

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

// SWEA_1238_Contact_D4_106ms 
public class Solution{
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int len, start, answer, max;
	static Queue<Integer> q;
	static ArrayList<Integer>[] graph;
	static int[] visited;
	
	public static void main(String[] args) throws IOException {
		
		for (int testCase = 1; testCase <= 10; testCase++) {
			
			st = new StringTokenizer(br.readLine());
			len = Integer.parseInt(st.nextToken()) / 2;
			start = Integer.parseInt(st.nextToken());
			st = new StringTokenizer(br.readLine());
			visited = new int[101];
			graph = new ArrayList[101];
			answer = 0;
			max = 0;
            
			for (int i = 0; i < 101; i++) { // ArrayList 배열생성
				graph[i] = new ArrayList<Integer>();
			}
			for (int i = 0; i < len; i++) { // 입력 받기
				graph[Integer.parseInt(st.nextToken())].add(Integer.parseInt(st.nextToken()));
			} 
            
            //BFS
			q = new LinkedList<Integer>();
			q.add(start);
			visited[start] = 1;
			while(!q.isEmpty()) {
				int x = q.poll();
				for (int i : graph[x]) {
					if (visited[i] == 0 ) {
						visited[i] = visited[x] + 1;
						q.add(i);
					}
				}
			}
            
            // BFS 종료 후 visited의 MAX를 찾음
			for (int i = 0; i < visited.length; i++) {
				if (visited[i] >= max) {
					max = visited[i];
					answer = answer < i ? i : answer;
				}
			}
			sb.append("#").append(testCase).append(" ").append(answer).append("\n");
			
		}
		
		System.out.print(sb.toString());
		
	}
	

}