https://www.acmicpc.net/problem/2660
월드컵 응원 모임이 있는데 서로 건너건너 아는 사이인 듯 하다. 그중에서 그 건너건너가 가장 작은 사람들을 골라서 건너건너의 길이의 최소값과 해당하는 사람들의 수, 그리고 해당 하는 사람들의 번호를 출력하는 문제이다.
from collections import defaultdict
n = int(input())
friend = defaultdict(list)
while True:
a, b = map(int, input().split())
if a == -1 and b == -1:
break
friend[a].append(b)
friend[b].append(a)
score = [100] * (n+1)
for i in range(1, n+1):
que = [(i, 0)]
idx = 0
visited = [True] * (n+1)
visited[i] = False
while idx < len(que):
now, count = que[idx]
idx += 1
for next in friend[now]:
if visited[next]:
visited[next] = False
que.append((next, count+1))
score[i] = max(que, key=lambda x: x[1])[1]
ans = min(score)
count = score.count(ans)
president = []
for idx, s in enumerate(score):
if s == ans:
president.append(idx)
print(ans, count)
print(" ".join(map(str, president)))
어제 풀었던 문제하고 비슷했던 것 같다. 건너건너의 길이를 저장하기 위해 que에 번호와 count를 저장하고, bfs가 끝나면 count의 최대값을 구해서 score라는 리스트에 저장했다.
마지막으로 score의 최소값을 구하고 최속밧의 개수와 해당 하는 사람들을 뽑아서 출력했다.
const input = require('fs').readFileSync(process.platform === 'linux'
? "/dev/stdin" : "./input.txt")
.toString()
.trim()
.split("\n")
.map((x) => x.split(" ").map(Number));
const n = input[0][0]
const friend = Array.from({ length: n + 1 }, () => Array())
for (let i = 1; i < input.length - 1; i++) {
[a, b] = input[i];
friend[a].push(b);
friend[b].push(a);
}
const score = Array(n + 1).fill(100);
for (let i = 1; i <= n; i++) {
const que = [[i, 0]]
let idx = 0;
const visited = Array(n + 1).fill(true);
visited[i] = false;
while (idx < que.length) {
const [now, count] = que[idx++];
friend[now].forEach((val, idx) => {
if (visited[val]) {
visited[val] = false;
que.push([val, count + 1]);
}
})
}
score[i] = Math.max(...que.map((x) => x[1]));
}
const ans = Math.min(...score);
let count = 0;
const candi = [];
for (let i = 1; i <= n; i++) {
if (score[i] === ans) {
count++;
candi.push(i);
}
}
console.log(ans, count);
console.log(candi.join(" "));
로직은 python의 로직을 그대로 가져왔다. 일부 메서드 사용만 조금 달라졌다.
백준에서 input하는건 아직도 적응 안 된다. 그리고 score의 최소값 뽑을 때나 que에서 최대값 뽑을 때 python처럼 그냥 넣었는데 그러면 안 된다는 것을 기억 못해서 한참 헤맸다.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
scanner.nextLine();
ArrayList<ArrayList<Integer>> friend = new ArrayList<>(n+1);
for(int i=0;i<=n;i++){
friend.add(new ArrayList<>());
}
while(true){
String[] line = scanner.nextLine().trim().split(" ");
int a= Integer.parseInt(line[0]);
int b= Integer.parseInt(line[1]);
if(a == -1 && b == -1){
break;
}
friend.get(a).add(b);
friend.get(b).add(a);
}
int[] score = new int[n+1];
for(int i=0;i<n+1;i++){
score[i] = 100;
}
for(int i=1;i<n+1;i++){
ArrayList<int[]> que = new ArrayList<>();
que.add(new int[]{i,0});
int idx = 0;
boolean[] visited = new boolean[n+1];
for(int v=0;v<=n;v++){
visited[v] = true;
}
visited[i] = false;
while(idx < que.size()){
int[] now = que.get(idx++);
ArrayList<Integer> next = friend.get(now[0]);
for(Integer ne : next){
if(visited[ne]){
visited[ne] = false;
que.add(new int[]{ne, now[1] + 1});
}
}
}
int s = 0;
for(int[] q:que){
if(s < q[1]){
s = q[1];
}
}
score[i] = s;
}
int ans = Arrays.stream(score).min().getAsInt();
int count = 0;
ArrayList<Integer> candi = new ArrayList<>();
for(int i=1;i<=n;i++){
if(score[i] == ans){
count++;
candi.add(i);
}
}
System.out.printf("%d %d\n",ans, count);
String answer = "";
for(int c : candi){
answer += c + " ";
}
System.out.println(answer);
scanner.close();
}
}
가장 오래걸렸다. python이나 js처럼 대충 배열 선언하면 알아서 꺼내 쓸 수 있을 줄 알았는데 일일이 new ArrayList로 선언해줘야하는 거를 몰랐어서 GPT의 도움을 받아서 해결했다.
그리고 fill이나 max로 알아서 되던 python이나 js와 다르게 for문으로 일일이 확인해야하는게 불편했다.