mingssssss

1. 문제

https://www.acmicpc.net/submit/1389/42916978

2. 코드

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

public class Main {
    
    // 전역 변수 설정
	static int[][] map;
	static int[] answer;
	static boolean[][] visited;
	static int temp;
	static int result = 999999999;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		map = new int[N + 1][N + 1];
        
		int M = Integer.parseInt(st.nextToken());

		for (int i = 0; i < M; i++) {

			st = new StringTokenizer(br.readLine());

			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());

			map[r][c] = 1;
			map[c][r] = 1;
		}
		// 입력 종료 && 인접 행렬 생성 종료
		
        // 1 ~ N까지 (노드 전체) 탐색 시작
		for (int k = 1; k < N + 1; k++) {

			Queue<Integer> q = new LinkedList<>();
			int[] answer = new int[N + 1];
			visited = new boolean[N + 1][N + 1]; // 각 노드를 돌 때마다 방문체크를 해줘야 하므로 초기화
			
			q.add(k);

			while (!q.isEmpty()) {

				int v = q.poll();

				for (int i = 1; i < N + 1; i++) {

					if (visited[v][i] == false && map[v][i] == 1) {
                            
                        // 양방향 방문체크
						visited[v][i] = true;
						visited[i][v] = true;
                            
						if (answer[i] == 0) {
							answer[i] = answer[v] + 1; // 현재 노드로부터 거리 1 추가
						}
						q.add(i);

					}

				}
			}
			
			
			// 각 노드의 최댓값 설정
			int check = 0;
			for (int i = 1; i < answer.length; i++) {
				check += answer[i];
//				System.out.printf("%d ", answer[i]);
			}
//			System.out.println();
			
			
			if (check < result) {
				result = check;
				temp = k;
			}

			
//			result = check < result ? check : result;
		}


		System.out.println(temp);

	}

}

3. 리뷰

1부터 N번 노드까지 각 노드까지의 거리를 구하고,

그 거리들의 합을 구해서 최소가 되는 노드를 구하는 문제이다.

인접 행렬을 만들고, 1번 노드부터 N번 노드까지 거리를 구하고

각각의 노드의 거리의 합을 구한다.

거리를 구하는 저 로직을 잘 익혀두어서 써먹을 수 있도록 연습해야겠다.