[D4-JAVA] SWEA 1238 - Contact

SW Expert Academy

 

✅ 문제 요약

시작노드에서부터 탐색을 시작하여 가장 깊은 노드를 찾고 만약 깊이가 같다면 노드의 번호가 더 큰 것을 출력하라

 

🤔 문제 접근

어렵지 않은 문제였으나 문제를 제대로 읽지 않아서 중간에 살짝 헤맸던 문제다. 항상 문제와 주어지는 조건을

잘 읽은 뒤 문제를 풀도록 해야겠다. (매번 이런 생각을 하지만 풀이법이 떠오르면 바로 코드부터 치고자 해서

잘 지켜지지 않는다..)

 

지금까지 풀어오던 그래프 문제와 다르게 정점 연결 정보를 특이하게 준다.

하지만 어려울거 없다. 정점 연결 정보는 항상 시작과 끝, 2가지가 한 쌍으로 주어지므로

각 테스트 케이스 별로 주어지는 (입력 받는 데이터 길이) / 2 만큼 StringTokenizer을 통해

정점 연결 정보를 받으면 된다.

 

정점 연결 정보를 담는 자료구조로는 임의로 생성한 Node 클래스 데이터 형식으로 사용하는

ArrayList<Node>[ ] 배열을 사용했다.

이유는 A정점에서 B정점으로 가는 정보도 저장해야 하며 어떤 정점의 depth또한 저장해야 했기 때문이다.

 

그래프 탐색은 너비 우선 탐색 BFS를 사용했으며 DFS로 풀진 않았지만 DFS로도 풀 수 있어보인다.

BFS 방식으로 풀기 위해 Queue를 사용했으며 Queue에 저장되는 데이터 형식은 Node 클래스로 설정했다.

 

초기, 시작노드의 depth를 1로 하여 큐에 삽입하고 현재 노드로부터 갈 수 있는 다른 노드들에 현재 노드의

depth+1을 저장하고 큐에 삽입했다. 매번 큐에서 현재 노드를 꺼내올 때마다 현재 깊이가 highdepth보다 크면

현재 depth와 node번호를 저장하고 만약 깊이가 같다면 현재 노드가 저장해놓은 노드 번호보다 클 때,

node번호를 갱신해주었다.

 

🚨CODE

import java.util.*;
import java.io.*;

public class Solution {
	static int nodeCount;
	static ArrayList<Node>[] list;
	static boolean[] visit;
	static int answer;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int test_case = 10;
		for(int t = 1; t<=test_case; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());

			nodeCount = Integer.parseInt(st.nextToken());
			int startNode = Integer.parseInt(st.nextToken());
			
			list = new ArrayList[101];
			visit = new boolean[101];
			for(int i = 1; i<=100; i++) {
				list[i] = new ArrayList<>();
			}
			
			st = new StringTokenizer(br.readLine());
			for(int i = 0; i<nodeCount/2; i++) {
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				list[a].add(new Node(b, 0));
			}
			
			answer = bfs(startNode);
			
			bw.write(String.format("#%d %d\n", t, answer));
		}// end of tc
		bw.flush();
	}
	public static int bfs(int startNode) {
		Queue<Node> q = new LinkedList<>();
		q.add(new Node(startNode, 1));
		int highDepth = -1;
		int highDepthNode = -1;
		
		while(!q.isEmpty()) {
			Node poll = q.poll();
			int curNode = poll.end;
			int curDepth = poll.depth;
			
			if(visit[curNode]) continue;
			visit[curNode] = true;
			
			// 가장 깊은 깊이 갱신
			// 만약 현재 깊이가 highDepth와 같은 경우
			if(highDepth == curDepth) {
				// 현재 노드 번호가 가장 깊은 노드번호보다 큰 경우
				if(curNode > highDepthNode) {
					highDepthNode = curNode;
				}
			}else if(curDepth > highDepth) {
				highDepthNode = curNode;
				highDepth = curDepth;
			}
			
			for(Node next : list[curNode]) {
				q.add(new Node(next.end, curDepth+1));
			}
			
		}
		return highDepthNode;
	}
}
class Node{
	int end;
	int depth;
	Node(int end, int depth){
		this.end = end;
		this.depth = depth;
	}
}