[SWEA] Contact

👀 문제 설명

문제

로그인해야 문제를 볼 수 있다.

 

✍🏻풀이

BFS (큐)를 사용해 문제를 풀었다.

인접 행렬 map을 사용해 그래프가 서로 연결되어 있는 상태를 나타낸다.

visited 배열을 사용해 시작점부터 i까지 오는 데 걸리는 횟수를 저장한다. visited[i]가 0이라면, 아직 방문을 하지 않은 것으로 판단한다.

 

BFS는 큐를 사용해 푸는 방법이므로, 제일 먼저 시작점 (시작 사람)의 번호를 넣어준다.

while문을 통해 큐가 비어있지 않을 동안, 큐의 가장 앞의 값을 가져오고, 그 값과 연결된 값들이면서 아직 방문하지 않은 점을 다시 큐에 넣는다. 이 때, visited[to] 값은 visited[from] + 1로 설정한다.

while문을 빠져나온 후, visited 배열을 확인하면서 가장 큰 값중, 수가 가장 큰 것을 찾아 출력하면 된다.

 

코드

package swea;

// Contact (https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15B1cKAKwCFAYD&categoryId=AV15B1cKAKwCFAYD&categoryType=CODE&problemTitle=contact&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 )

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

public class SWEA_1238 {
	
	private static int inputNum, start; // 입력받을 데이터의 수, 시작점 값
	private static int[][] map; // 인접 행렬
	private static int[] visited; // 시작점부터 i까지 오는데 걸린 횟수, visited[i]가 0이면, 아직 방문을 하지 않은 것이다.
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		for (int tc = 1; tc <= 10; tc++) {
			// input
			st = new StringTokenizer(br.readLine());
			
			inputNum = Integer.parseInt(st.nextToken());
			start = Integer.parseInt(st.nextToken());
			
			map = new int[inputNum + 1][inputNum + 1];
			visited = new int[inputNum + 1];
			
			st = new StringTokenizer(br.readLine());
			
			for (int input = 1; input <= inputNum; input += 2) {
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());
				
				if (map[from][to] != 1) map[from][to] = 1;
			}
			
			// solve
			bw.write("#" + tc + " " + BFS() + "\n");
		}

		bw.flush();
		bw.close();
	}

	private static int BFS() {
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(start);
		
		while (!queue.isEmpty()) {
			int from = queue.poll();
			
			for (int to = 1; to <= inputNum; to++) {
				if (map[from][to] == 1 && visited[to] == 0) {
					visited[to] = visited[from] + 1;
					queue.offer(to);
				}
			}
		}
		
		// 가장 마지막에 도착한 사람들 중, 번호의 최댓값 구하기
		int maxLen = 0;
		int ans = 0;
		for (int i = 1; i <= inputNum; i++) {
			if (maxLen <= visited[i]) {
				maxLen = visited[i];
				ans = i;
			}
		}
		
		return ans;
	}
	
}