결혼식 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 24428 11176 9099 45.402% 문제 상근이는 자신의…
- User
결혼식 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 24428 11176 9099 45.402% 문제 상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.
상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.
입력 첫째 줄에 상근이의 동기의 수 n (2 ≤ n ≤ 500)이 주어진다. 둘째 줄에는 리스트의 길이 m (1 ≤ m ≤ 10000)이 주어진다. 다음 줄부터 m개 줄에는 친구 관계 ai bi가 주어진다. (1 ≤ ai < bi ≤ n) ai와 bi가 친구라는 뜻이며, bi와 ai도 친구관계이다.
출력 첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.
예제 입력 1 6 5 1 2 1 3 3 4 2 3 4 5 예제 출력 1 3 예제 입력 2 6 5 2 3 3 4 4 5 5 6 2 5 예제 출력 2 0
// #include <bits/stdc++.h> using namespace std; #include #include #include #include #include #include
int n, m; queue todo; vector adj[501]; bool visited[501];
int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m; for (int i = 1; i <= m; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); }
// DFS stack todo; todo.push(1); int ret = 0; visited[1] = true; while (!todo.empty()) { int curr = todo.top(); todo.pop();
for (int i : adj[curr]) { if (visited[i]) { continue; } visited[i] = true; ret++; todo.push(i); }}
cout << ret;
return 0; }
왜??
- Assistant
위 코드에서는 "상근이(1번 학생)의 친구 및 친구의 친구까지 초대"한다는 조건을 잘못 처리하고 있어서 문제의 조건을 정확히 반영하지 못하고 있습니다.
🔍 문제 요약
- 총 N명의 동기가 있고, 번호는 1부터 N.
- 상근의 번호는 1번.
- 상근은 "자신의 친구(1촌)" 와 "친구의 친구(2촌)"까지만 초대.
- 이때 자신(1번)은 제외하고 초대 인원을 출력해야 함.
❗ 현재 코드의 문제점
작성한 코드는 DFS로 상근이와 연결된 모든 노드를 다 방문하기 때문에 1촌도 2촌도 아닌 n촌까지 초대하게 됩니다. 즉, 문제의 조건(딱 2단계까지) 를 무시한 BFS/DFS 완전 탐색입니다.
예를 들어
1-2-3-4-5로 이어진 경우,4,5까지도 전부 방문하는 오류입니다.
✅ 해결 방법: BFS로 거리(깊이) 제한 두기
- BFS를 써서 거리(Depth 또는 Level)가 2 이하인 노드까지만 방문.
- Level 1: 친구
- Level 2: 친구의 친구
✅ 수정된 코드 (BFS, 거리 제한으로 정확히 1촌, 2촌만 포함)
#include <bits/stdc++.h> using namespace std; int n, m; vector<int> adj[501]; bool visited[501]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } queue<pair<int, int>> q; // (노드, 깊이) q.push({1, 0}); visited[1] = true; int cnt = 0; while (!q.empty()) { int curr = q.front().first; int depth = q.front().second; q.pop(); if (depth >= 2) continue; // 2촌까지만 허용 for (int next : adj[curr]) { if (!visited[next]) { visited[next] = true; cnt++; q.push({next, depth + 1}); } } } cout << cnt; return 0; }
🔍 로직 설명
- BFS를 사용해서 상근이(1번)부터 탐색.
- 현재 노드의 depth가 2 이상이면 더 이상 그 아래로 탐색하지 않음.
- 방문하지 않은 친구이면
visited표시하고, 초대 인원cnt++.
✅ 예제 테스트
예제 1
입력:
6 5 1 2 1 3 3 4 2 3 4 5상근이(1)의 친구: 2, 3
2,3의 친구 (친구의 친구): 4
→ 초대 인원: 2,3,4 → 총 3명출력 결과: ✅
3
예제 2
입력:
6 5 2 3 3 4 4 5 5 6 2 5상근이(1)는 친구 없음 → 초대 인원: 0명
출력 결과: ✅
0
📌 요약
- 친구 및 친구의 친구까지만 초대 = 깊이 2 이하인 노드만 카운팅.
- 현재 DFS 로직은 모든 깊이를 탐색해서 틀린 풀이.
- BFS로 거리 제한을 주는 방식으로 수정하면 통과됩니다.
필요하시면 DFS 방식으로 수정된 정답 코드도 드릴 수 있어요!
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.