[SWEA] - Contact / 1238번 (Java)

[SWEA] - Contact / 1238번 (Java)

[SWEA] - Contact / 1238번 (Java)

1. 문제 접근

그래프(비상 연락망)에 대한 정보가 주어질 때, 마지막에 동시에 연락받은 사람(노드)들 중 가장 번호가 큰 사람을 구하면 된다.

 

`startPoint`부터 연락이 동시에 전파된다는 것을 통해 BFS로 구현하였다.

 

구해야하는 것은 `startPoint`로 부터 가장 마지막에 연락을 받은 사람들의 정보인데, 이는 `startPoint`로부터 가장 멀리 떨어져 있는(거리가 먼) 사람들과 동일하다.

 

따라서 BFS 탐색을 진행하며 Queue에 인접 노드를 삽입할 때, 거리 정보(`dist[]`)를 함께 저장했다.

 

또한 최대거리를 한번에 구하기 위해 `maxDist`값 역시 동시에 갱신했다.

 

while (!q.isEmpty()) {
    int currNode = q.poll();
    for (int nextNode : adList[currNode]) {
        if (isVisited[nextNode])
            continue;
        q.offer(nextNode);
        isVisited[nextNode] = true;
        // 거리 함께 저장
        dist[nextNode] = dist[currNode] + 1;
        maxDist = Math.max(maxDist, dist[nextNode]);
    }
}

 

모든 BFS 탐색이 종료되면, `maxDist`와 동일한 거리만큼 떨어져있는 노드 중 큰 값을 구하기 위해 반복문을 통해 정답을 구했다.

 

// 최대 거리 + 최대 번호 노드 검색
int ans = -1;
for(int nodeNum = 1;nodeNum<101;++nodeNum) {
    if(dist[nodeNum]==maxDist && ans<nodeNum)
        ans = nodeNum;
}

---

2. 코드

package swea;

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

/**
 * [SWEA] - Contact / 1238번
 * @author JinHxxxxKim
 * 
 * 1. 입력 받는 데이터의 길이와 시작점을 입력받는다.
 * 2. 그래프 정보를 입력받아 유향 그래프를 완성한다.
 * 3. 시작점에서 부터 BFS 탐색을 시작한다.
 * 		- 시작점의 Dist값은 0으로 설정한다.
 * 		- Queue에 삽입할 때, Dist값을 함께 계산해서 저장한다.
 * 4. maxDist 와 동일한 거리에 있는 노드 중 노드 번호가 가장 큰 노드를 출력한다.
 * 
 */
public class Sol_1238 {
	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	private static StringBuilder sb = new StringBuilder();
	private static StringTokenizer st;
	
	private static int startPoint; // 시작점
	private static int N; // 노드의 개수
	private static List<Integer>[] adList; // 인접 리스트
	private static int[] dist; // 거리 저장 배열
	private static boolean[] isVisited; // 방문 여부 확인 배열
	private static int maxDist; // 최대 거리
	
	public static void main(String[] args) throws Exception {
		int TC = 10;
		for (int testCase = 1; testCase <= TC; testCase++) {
			st = new StringTokenizer(br.readLine().trim());
			int len = Integer.parseInt(st.nextToken());
			startPoint = Integer.parseInt(st.nextToken());
			
			N = len / 2;
			adList = new List[101];
			for (int node = 0; node < 101; ++node) {
				adList[node] = new ArrayList<Integer>();
			}
			
			st = new StringTokenizer(br.readLine().trim());
			// 인접리스트 생성
			for(int idx = 0;idx<N;++idx) {
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());
				// 유향 그래프
				adList[from].add(to);
			}
			
			dist = new int[101];
			isVisited = new boolean[101];
			maxDist = 0;
			
			// 탐색 시작
			contact(startPoint);
			// 최대 거리 + 최대 번호 노드 검색
			int ans = -1;
			for(int nodeNum = 1;nodeNum<101;++nodeNum) {
				if(dist[nodeNum]==maxDist && ans<nodeNum)
					ans = nodeNum;
			}
			sb.append(String.format("#%d %d\n", testCase, ans));
		}
		System.out.println(sb);
	}

	// BFS 탐색
	private static void contact(int startPoint) {
		Queue<Integer> q = new ArrayDeque<>();
		q.offer(startPoint);
		isVisited[startPoint] = true;
		dist[startPoint] = 0;
		while (!q.isEmpty()) {
			int currNode = q.poll();
			for (int nextNode : adList[currNode]) {
				if (isVisited[nextNode])
					continue;
				q.offer(nextNode);
				isVisited[nextNode] = true;
				// 거리 함께 저장
				dist[nextNode] = dist[currNode] + 1;
				maxDist = Math.max(maxDist, dist[nextNode]);
			}
		}
	}
}

---

3. 디버깅

"연락 인원은 최대 100명이며, 부여될 수 있는 번호는 1이상, 100이하이다."라는 제약사항이 존재한다.

 

따라서 노드의 개수를 100개로 고정한 뒤, 입력이 들어오는 번호에 대해 인접리스트를 추가하는 방식으로 구성해야한다.

 

---

4. 결과