어느 모임에 사람이 n명 있고 1번부터 n번까지 번호가 붙어 있다.
친구 관계가 m줄 주어진다. 한 줄 "a b"는 a번과 b번이 서로 친구라는 뜻이다.
같은 관계가 여러 줄에 나올 수 있고, "a b"와 "b a"로 순서만 바뀌어 나올 수도 있다. 몇 번 나오든 두 사람은 친구 한 쌍일 뿐이다.
x번에게 새 친구를 한 명 추천하려고 한다.
추천 후보는 x번 자신이 아니고 x번의 친구도 아닌 사람이다.
후보 y의 점수는 x번과도 친구이고 y번과도 친구인 사람의 수이다.
점수가 1 이상인 후보 가운데 점수가 가장 큰 사람을 추천한다. 점수가 같으면 번호가 가장 작은 사람을 추천한다.
물음이 q개 주어진다. 물음마다 x가 하나씩 주어지고, 같은 사람을 여러 번 물을 수도 있다.
물음마다 한 줄에 추천할 사람의 번호와 그 점수를 빈칸 하나로 띄워 출력하라.
점수가 1 이상인 후보가 없으면 그 줄에 -1만 출력한다.
입력
첫 줄에 n, m, q가 빈칸 하나로 나뉘어 주어진다. 이어서 m줄에 a와 b가 한 줄에 한 쌍씩 빈칸 하나로 나뉘어 주어진다. 마지막 줄에 물음 x가 q개 빈칸 하나로 나뉘어 주어진다. 2 ≤ n ≤ 10,000, 0 ≤ m ≤ 10,000, 1 ≤ q ≤ 100, 1 ≤ a, b, x ≤ n, a ≠ b. 모두 정수다
출력
물음마다 한 줄씩 모두 q줄. 추천할 사람의 번호와 점수, 없으면 -1
예시 1 · stdin
7 8 4
1 2
1 3
2 4
3 4
2 5
3 5
4 6
2 1
1 6 7 2
stdout
4 2
2 1
-1
3 3
예시 2 · stdin
4 5 2
1 2
2 3
3 1
1 2
2 1
1 4
stdout
-1
-1
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
그래프를 사람마다 친구 목록(인접 목록)으로 두면 '친구의 친구'를 두 겹 반복으로 훑을 수 있어요. x의 친구 f마다 f의 친구 y를 보면서 y의 점수를 1씩 올리면, y가 f를 거쳐 x와 이어진 횟수가 곧 함께 아는 친구 수예요. 첫 예시에서 1번의 친구는 2, 3이고 4번과 5번이 둘 다 2점이라 번호가 작은 4번을 추천해요. 함정 하나: 같은 관계가 여러 번 나와요(첫 예시의 1 2와 2 1). 그대로 목록에 넣으면 같은 친구가 두 번 들어가 점수가 두 번 올라가요. Python set, JavaScript·TypeScript Set, Java·C# HashSet은 넣기만 하면 겹친 것이 한 번만 남아요. C++는 vector를 sort한 다음 unique와 erase로 겹친 것을 잘라 내고, C는 관계를 a * (n + 1) + b 한 수로 적어 qsort한 다음 바로 앞과 같은 것을 건너뛰어요. 크레이콘은 사전()에 본 관계를 적어 두고 있나로 물어봐요. 함정 둘: 관계는 양쪽이에요. a의 목록에 b만 넣고 b의 목록에 a를 안 넣으면 반쪽 그래프가 돼요. 함정 셋: 친구의 친구에는 언제나 x 자신이 들어 있어요(x → f → x). 빼지 않으면 x가 자기 자신을 추천받아요. 함정 넷: 이미 친구인 사람도 친구의 친구일 수 있으니 후보에서 빼야 해요(둘째 예시의 1번은 2, 3번이 서로 친구지만 추천할 사람이 없어요). 함정 다섯: 점수가 같으면 번호가 작은 사람이에요. Set이나 사전을 도는 차례는 번호 순이 아니니 y < best를 직접 견줘야 해요. 함정 여섯: 점수 배열을 물음마다 다시 쓰는 풀이(Java, C, C++, 크레이콘)는 건드린 칸을 0으로 되돌려야 해요. 배열 전체를 지우면 물음마다 n칸을 돌게 되니, 건드린 사람만 따로 모아 두었다가 그 칸만 지워요. Python·JavaScript·TypeScript·C#은 물음마다 사전(dict, Map, Dictionary)을 새로 만들어서 지울 것이 없어요. 없는 열쇠의 기본값은 Python common.get(y, 0), JavaScript common.get(y) ?? 0, C# GetValueOrDefault(y)로 얻어요.
Pythonmain.py · 28 줄
import sysdata = sys.stdin.read().split()n, m, q = int(data[0]), int(data[1]), int(data[2])# 인접 목록을 집합으로: friends[p] = p의 친구들. 같은 관계가 또 나와도 집합에는 한 번만 들어간다friends = [set() for _ in range(n + 1)]for i in range(m): a, b = int(data[3 + 2 * i]), int(data[4 + 2 * i]) friends[a].add(b) friends[b].add(a)out = []for k in range(q): x = int(data[3 + 2 * m + k]) # 친구의 친구를 모두 훑으며 후보마다 '함께 아는 친구' 수를 센다 common = {} for f in friends[x]: for y in friends[f]: if y != x and y not in friends[x]: # 자기 자신과 이미 친구인 사람은 후보가 아니다 common[y] = common.get(y, 0) + 1 if not common: out.append("-1") continue # 점수가 큰 사람, 같으면 번호가 작은 사람 best = min(common, key=lambda y: (-common[y], y)) out.append(f"{best} {common[best]}")print("\n".join(out))
JavaScriptmain.js · 35 줄
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m, q] = data;// 인접 목록을 Set으로: friends[p] = p의 친구들. 같은 관계가 또 나와도 Set에는 한 번만 들어간다const friends = Array.from({ length: n + 1 }, () => new Set());for (let i = 0; i < m; i++) { const a = data[3 + 2 * i]; const b = data[4 + 2 * i]; friends[a].add(b); friends[b].add(a);}const out = [];for (let k = 0; k < q; k++) { const x = data[3 + 2 * m + k]; // 친구의 친구를 모두 훑으며 후보마다 '함께 아는 친구' 수를 센다 const common = new Map(); for (const f of friends[x]) { for (const y of friends[f]) { // 자기 자신과 이미 친구인 사람은 후보가 아니다 if (y !== x && !friends[x].has(y)) common.set(y, (common.get(y) ?? 0) + 1); } } // 점수가 큰 사람, 같으면 번호가 작은 사람 let best = -1; let bestCount = 0; for (const [y, c] of common) { if (c > bestCount || (c === bestCount && y < best)) { best = y; bestCount = c; } } out.push(best === -1 ? "-1" : `${best} ${bestCount}`);}console.log(out.join("\n"));
TypeScriptmain.ts · 37 줄
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m, q] = data;// 인접 목록을 Set으로: friends[p] = p의 친구들. 같은 관계가 또 나와도 Set에는 한 번만 들어간다const friends: Set<number>[] = Array.from({ length: n + 1 }, () => new Set<number>());for (let i = 0; i < m; i++) { const a = data[3 + 2 * i]; const b = data[4 + 2 * i]; friends[a].add(b); friends[b].add(a);}const out: string[] = [];for (let k = 0; k < q; k++) { const x = data[3 + 2 * m + k]; // 친구의 친구를 모두 훑으며 후보마다 '함께 아는 친구' 수를 센다 const common = new Map<number, number>(); for (const f of friends[x]) { for (const y of friends[f]) { // 자기 자신과 이미 친구인 사람은 후보가 아니다 if (y !== x && !friends[x].has(y)) common.set(y, (common.get(y) ?? 0) + 1); } } // 점수가 큰 사람, 같으면 번호가 작은 사람 let best = -1; let bestCount = 0; for (const [y, c] of common) { if (c > bestCount || (c === bestCount && y < best)) { best = y; bestCount = c; } } out.push(best === -1 ? "-1" : `${best} ${bestCount}`);}console.log(out.join("\n"));
JavaMain.java · 54 줄
import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); st.nextToken(); int n = (int) st.nval; st.nextToken(); int m = (int) st.nval; st.nextToken(); int q = (int) st.nval; // 인접 목록을 HashSet으로: friends.get(p) = p의 친구들. 같은 관계가 또 나와도 한 번만 들어간다 List<Set<Integer>> friends = new ArrayList<>(); for (int p = 0; p <= n; p++) friends.add(new HashSet<>()); for (int i = 0; i < m; i++) { st.nextToken(); int a = (int) st.nval; st.nextToken(); int b = (int) st.nval; friends.get(a).add(b); friends.get(b).add(a); } int[] common = new int[n + 1]; // common[y] = 지금 물음에서 y와 함께 아는 친구 수 StringBuilder sb = new StringBuilder(); for (int k = 0; k < q; k++) { st.nextToken(); int x = (int) st.nval; Set<Integer> mine = friends.get(x); // 친구의 친구를 모두 훑으며 후보마다 '함께 아는 친구' 수를 센다 List<Integer> touched = new ArrayList<>(); for (int f : mine) { for (int y : friends.get(f)) { if (y == x || mine.contains(y)) continue; // 자기 자신과 이미 친구인 사람은 후보가 아니다 if (common[y]++ == 0) touched.add(y); } } // 점수가 큰 사람, 같으면 번호가 작은 사람 int best = -1, bestCount = 0; for (int y : touched) { if (common[y] > bestCount || (common[y] == bestCount && y < best)) { best = y; bestCount = common[y]; } common[y] = 0; // 다음 물음을 위해 센 것을 지운다 } if (best == -1) sb.append("-1\n"); else sb.append(best).append(' ').append(bestCount).append('\n'); } System.out.print(sb); }}
C#Main.cs · 51 줄
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { var data = Console.In.ReadToEnd().Split((char[]?)null, StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(data[0]), m = int.Parse(data[1]), q = int.Parse(data[2]); // 인접 목록을 HashSet으로: friends[p] = p의 친구들. 같은 관계가 또 나와도 한 번만 들어간다 var friends = new HashSet<int>[n + 1]; for (int p = 0; p <= n; p++) friends[p] = new HashSet<int>(); for (int i = 0; i < m; i++) { int a = int.Parse(data[3 + 2 * i]), b = int.Parse(data[4 + 2 * i]); friends[a].Add(b); friends[b].Add(a); } var sb = new StringBuilder(); for (int k = 0; k < q; k++) { int x = int.Parse(data[3 + 2 * m + k]); // 친구의 친구를 모두 훑으며 후보마다 '함께 아는 친구' 수를 센다 var common = new Dictionary<int, int>(); foreach (int f in friends[x]) { foreach (int y in friends[f]) { if (y == x || friends[x].Contains(y)) continue; // 자기 자신과 이미 친구인 사람은 후보가 아니다 common[y] = common.GetValueOrDefault(y) + 1; } } // 점수가 큰 사람, 같으면 번호가 작은 사람 int best = -1, bestCount = 0; foreach (var (y, c) in common) { if (c > bestCount || (c == bestCount && y < best)) { best = y; bestCount = c; } } if (best == -1) sb.Append("-1\n"); else sb.Append(best).Append(' ').Append(bestCount).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 54 줄
#include <algorithm>#include <iostream>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, q; cin >> n >> m >> q; // 인접 목록: friends[p] = p의 친구들 vector<vector<int>> friends(n + 1); for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; friends[a].push_back(b); friends[b].push_back(a); } // 같은 관계가 여러 번 나올 수 있다: 정렬한 다음 unique로 겹친 것을 뒤로 몰고 erase로 잘라 낸다 for (auto &list : friends) { sort(list.begin(), list.end()); list.erase(unique(list.begin(), list.end()), list.end()); } vector<int> common(n + 1, 0); // common[y] = 지금 물음에서 y와 함께 아는 친구 수 vector<int> touched; for (int k = 0; k < q; k++) { int x; cin >> x; const vector<int> &mine = friends[x]; // 친구의 친구를 모두 훑으며 후보마다 '함께 아는 친구' 수를 센다 touched.clear(); for (int f : mine) { for (int y : friends[f]) { // 자기 자신과 이미 친구인 사람은 후보가 아니다(정렬해 두었으니 이분 탐색으로 찾는다) if (y == x || binary_search(mine.begin(), mine.end(), y)) continue; if (common[y]++ == 0) touched.push_back(y); } } // 점수가 큰 사람, 같으면 번호가 작은 사람 int best = -1, bestCount = 0; for (int y : touched) { if (common[y] > bestCount || (common[y] == bestCount && y < best)) { best = y; bestCount = common[y]; } common[y] = 0; // 다음 물음을 위해 센 것을 지운다 } if (best == -1) cout << "-1\n"; else cout << best << ' ' << bestCount << '\n'; } return 0;}
Cmain.c · 65 줄
#include <stdio.h>#include <stdlib.h>static int cmp_int(const void *p, const void *q) { int a = *(const int *)p, b = *(const int *)q; return (a > b) - (a < b);}int main(void) { int n, m, q; if (scanf("%d %d %d", &n, &m, &q) != 3) return 0; // 관계 "a b"를 양쪽 방향의 수 두 개로 적는다: a * (n + 1) + b와 b * (n + 1) + a (1억 남짓이라 int에 든다) int *key = malloc((2 * m + 1) * sizeof(int)); for (int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); key[2 * i] = a * (n + 1) + b; key[2 * i + 1] = b * (n + 1) + a; } // 정렬하면 같은 사람의 친구가 모이고, 같은 관계는 바로 옆에 붙으니 하나만 남긴다 qsort(key, 2 * m, sizeof(int), cmp_int); int *to = malloc((2 * m + 1) * sizeof(int)); // 친구 번호를 사람 차례로 이어 놓은 것 int *start = calloc(n + 2, sizeof(int)); // p의 친구는 to[start[p]] … to[start[p + 1] - 1] int edges = 0; for (int i = 0; i < 2 * m; i++) { if (i > 0 && key[i] == key[i - 1]) continue; to[edges++] = key[i] % (n + 1); start[key[i] / (n + 1) + 1]++; } for (int p = 1; p <= n + 1; p++) start[p] += start[p - 1]; int *common = calloc(n + 1, sizeof(int)); // common[y] = 지금 물음에서 y와 함께 아는 친구 수 int *is_friend = calloc(n + 1, sizeof(int)); // is_friend[y] = 1이면 x의 친구 int *touched = malloc((n + 1) * sizeof(int)); for (int k = 0; k < q; k++) { int x; scanf("%d", &x); for (int e = start[x]; e < start[x + 1]; e++) is_friend[to[e]] = 1; // 친구의 친구를 모두 훑으며 후보마다 '함께 아는 친구' 수를 센다 int cnt = 0; for (int e = start[x]; e < start[x + 1]; e++) { int f = to[e]; for (int g = start[f]; g < start[f + 1]; g++) { int y = to[g]; if (y == x || is_friend[y]) continue; // 자기 자신과 이미 친구인 사람은 후보가 아니다 if (common[y]++ == 0) touched[cnt++] = y; } } // 점수가 큰 사람, 같으면 번호가 작은 사람 int best = -1, best_count = 0; for (int i = 0; i < cnt; i++) { int y = touched[i]; if (common[y] > best_count || (common[y] == best_count && y < best)) { best = y; best_count = common[y]; } common[y] = 0; // 다음 물음을 위해 센 것을 지운다 } for (int e = start[x]; e < start[x + 1]; e++) is_friend[to[e]] = 0; if (best == -1) printf("-1\n"); else printf("%d %d\n", best, best_count); } free(key); free(to); free(start); free(common); free(is_friend); free(touched); return 0;}
Craykonmain.cray · 79 줄
첫줄 = 콘솔.수들읽기();n = 첫줄[0];m = 첫줄[1];q = 첫줄[2];// 인접 목록: friends[p] = p의 친구들(목록은 10,000칸까지라 번호에서 1을 빼 0번부터 둔다)friends = [];반복 (p = 0; p < n; p++){ friends.넣기([]);}// 같은 관계가 또 나오면 넣지 않는다: 본 관계를 사전에 "작은 번호 * 10000 + 큰 번호"로 적어 둔다본관계 = 사전();반복 (i = 0; i < m; i++){ 쌍 = 콘솔.수들읽기(); a = 수학.작은수(쌍[0], 쌍[1]) - 1; b = 수학.큰수(쌍[0], 쌍[1]) - 1; 열쇠 = a * 10000 + b; 만약 (!본관계.있나(열쇠)) { 본관계[열쇠] = 참; friends[a].넣기(b); friends[b].넣기(a); }}common = 새목록(n, 0); // common[y] = 지금 물음에서 y와 함께 아는 친구 수isFriend = 새목록(n, 거짓); // isFriend[y] = x의 친구인가물음들 = 콘솔.수들읽기();각각 (물음 에서 물음들){ x = 물음 - 1; 각각 (f 에서 friends[x]) { isFriend[f] = 참; } // 친구의 친구를 모두 훑으며 후보마다 '함께 아는 친구' 수를 센다 touched = []; 각각 (f 에서 friends[x]) { 각각 (y 에서 friends[f]) { // 자기 자신과 이미 친구인 사람은 후보가 아니다 만약 (y != x && !isFriend[y]) { 만약 (common[y] == 0) { touched.넣기(y); } common[y] += 1; } } } // 점수가 큰 사람, 같으면 번호가 작은 사람 best = -1; bestCount = 0; 각각 (y 에서 touched) { 만약 (common[y] > bestCount || common[y] == bestCount && y < best) { best = y; bestCount = common[y]; } common[y] = 0; // 다음 물음을 위해 센 것을 지운다 } 각각 (f 에서 friends[x]) { isFriend[f] = 거짓; } 만약 (best == -1) { 콘솔.쓰기(-1); } 아니면 { 콘솔.쓰기(best + 1 + " " + bestCount); }}