mingssssss

1. 문제

https://www.acmicpc.net/problem/6118

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 ArrayList<ArrayList<Integer>> list;
	static boolean[] visited;
	static int cnt;
	static int[] answer;
	static int max;
	static boolean flag;

	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());
		int M = Integer.parseInt(st.nextToken());

		list = new ArrayList<>();
		visited = new boolean[N + 1];
		answer = new int[N + 1];
		
		for (int i = 0; i < N + 1; i++) {
			list.add(new ArrayList<>());
		}

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

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

			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			list.get(a).add(b);
			list.get(b).add(a);
		}
		// 입력 종료 && 인접 리스트 입력

		bfs(N, M, list, visited);
		
		int cnt = 0;
		for (int i = 1; i < N + 1; i++) {
			
			if (flag == false && answer[i] == max) {
				System.out.print(i + " ");
				flag = true;
			}
			if (answer[i] == max) {
				cnt++;
			}
		}
		System.out.print(max + " " + cnt);
//		System.out.println();
//		for (int i = 1; i < N + 1; i++) {
//			System.out.printf("%d ", answer[i]);
//		}

//		// 출력
//		for (int i = 0; i < N; i++) {
//			for (int j = 0; j < N; j++) {
//				System.out.printf("%d ", list.get(i).get(j));
//			}
//			System.out.println();
//		}
	}

	private static void bfs(int N, int M, ArrayList<ArrayList<Integer>> list, boolean[] visited) {

		Queue<Integer> q = new LinkedList<>();

		q.add(1);
		visited[1] = true;
		cnt = 0;

		while (!q.isEmpty()) {

			int now = q.poll();

			for (int next : list.get(now)) {

				if (visited[next] == false) {

					visited[next] = true;

					
					if (answer[next] == 0) {
						answer[next] = answer[now] + 1;
						max = answer[next];
					}
					q.add(next);
				}
			}

		}

	}

}

3. 리뷰

입력을 받아와서 인접 리스트를 구성하여

시작점인 1부터 돌면서 거리를 구하여 출력하는 문제이다.

처음에는 배열로 인접 행렬을 만들어서 제출했는데 메모리 초과가 났다.

이런 문제는 인접 리스트를 구성해서 푸는 것이 메모리나 시간 측면에서 좋을 것 같다.

ArrayList를 2차원으로 구성해서 인접리스트를 구성했다.

그 다음 1부터 Queue에 넣고 list를 순회하면서 방문하지 않았다면

방문처리를 해주고 answer 배열에 아직 값이 없다면(0이라면)

해당 노드의 거리를 현재 탐색하는 노드의 거리보다 1을 추가해서 저장한다.

마지막에 저장하는 answer 배열의 값이 최댓값이므로 max를 저장해준다.

이후 for문을 돌면서 max 값이면서 가장 처음에 나오는 인덱스를 저장해주고

다시 체크하지 않기 위해 boolean형 변수를 만들어서 다시 체크하지 않게 해줬다.

또한 max 값인 노드를 체크해주고 정답을 출력했다.