[SWEA] #1238 - Contact

※ 문제에 대한 저작권은 SW Expert Academy에 있습니다.

💡 출처

---

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

SW Expert Academy

 

💡 문제

---

[설명]

아래는 비상연락망을 나타낸 그림이다.

 
각 원은 개개인을 의미하며, 원 안의 숫자는 그 사람의 번호를 나타내고 빨간 원은 연락을 시작하는 당번을 의미한다.

화살표는 연락이 가능한 방향을 의미한다.

위의 예시에서는 7번과 1번은 서로 연락이 가능하다,

하지만 2번과 7번의 경우 2번은 7번에게 연락할 수 있지만 7번은 2번에게 연락할 수 없다.
 
비상연락망이 가동되면 아래 그림과 같이 연락을 시작하는 당번인 2번은 연락 가능한 7번과 15번에 동시에 연락을 취한다 (다자 간 통화를 사용한다고 가정).
 

 
그다음 아래와 같이 7번은 1번에게, 15번은 4번에게 연락을 취한다 (이 과정은 동시에 일어난다고 가정한다).
 

그다음 아래와 같이 1번은 8번과 17번에게 동시에 연락하며, 이와 동시에 4번은 10번에게 연락한다.

7번과 2번의 경우는 이미 연락을 받은 상태이기 때문에 다시 연락하지 않는다.
 

위의 모습이 연락이 끝난 마지막 모습이 되며, 마지막에 동시에 연락받은 사람은 8번, 10번, 17번의 세 명이다.

이 중에서 가장 숫자가 큰 사람은 17번이므로 17을 반환하면 된다.

 

💡 아이디어

---

BFS를 이용하면 문제를 간단하게 해결할 수 있다.

우선 시작점을 Queue에 넣는다. 그 후 Queue에서 하나를 꺼내 연결되어 있는 노드이면 visited값을 1씩 늘려준다.

그리고 max값을 현재의 visited값으로 지정한다.

이 과정을 Queue가 모두 빌 때까지 반복한다.

그리고 난 후 max값과 같은 visited값의 값 중에서 가장 큰 수를 가지는 노드를 출력하면 된다.

 

💡 소스코드

---

package SWEA;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class SWEA_P1238_Contact {

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("./SWEA_INPUT/SWEA_P1238_input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		for (int TC = 1; TC <= 10; TC++) {
			StringTokenizer sz = new StringTokenizer(br.readLine());
			int[][] G = new int[101][101];

			int Edge = Integer.parseInt(sz.nextToken());//간선의 수 
			int Start = Integer.parseInt(sz.nextToken());//시작점

			String[] s = br.readLine().split(" ");

			for (int i = 0; i < Edge; i += 2)
				G[Integer.parseInt(s[i])][Integer.parseInt(s[i + 1])] = 1;

			System.out.println("#" + TC + " " + solve(G, Start));

		}
		br.close();
	}

	public static int solve(int[][] G, int Start) {
		Queue<Integer> queue = new LinkedList<>();
		int[] visited = new int[G.length];
		int cur = Start;
		int max = 0;

		queue.add(Start);//시작점 queue에 add
		visited[Start] = 1;//시작점의 visited = 1

		while (!queue.isEmpty()) {//queue가 빌 때까지 반복
			cur = queue.poll();//queue에서 하나 꺼내고

			for (int i = 1; i < G.length; i++) {
				if (G[cur][i] == 1 && visited[i] == 0) {//cur에 연결된 노드가 있다면
					queue.add(i);//queue에 추가하고
					visited[i] = visited[cur] + 1;//레벨을 부여(시작점은 1, 그 이후로는 2, 3, 4...)
				}
			}

			max = visited[cur];//최대 레벨의 값
		}

		for (int j = G.length - 1; j >= 1; j--)
			if (visited[j] == max)//visited를 뒤에서부터 보면서 max를 가지는 지점을 확인
				return j;

		return -1;
	}
}

 

💡 결과

---