[BOJ] 2660 회장뽑기

이강혁·2024년 10월 30일
0

백준

목록 보기
26/36

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

월드컵 응원 모임이 있는데 서로 건너건너 아는 사이인 듯 하다. 그중에서 그 건너건너가 가장 작은 사람들을 골라서 건너건너의 길이의 최소값과 해당하는 사람들의 수, 그리고 해당 하는 사람들의 번호를 출력하는 문제이다.

Python

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의 최소값을 구하고 최속밧의 개수와 해당 하는 사람들을 뽑아서 출력했다.

Javascript

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처럼 그냥 넣었는데 그러면 안 된다는 것을 기억 못해서 한참 헤맸다.

Java

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문으로 일일이 확인해야하는게 불편했다.

profile
사용자불량
post-custom-banner

0개의 댓글