Skip to content
TheChatArchiveThe Chat Archive
chatgpt-4o-latest-20250326· OpenAIHugging Face LMArena Human Preference 140K

결혼식 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 24428 11176 9099 45.402% 문제 상근이는 자신의…

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with gpt-4.1-mini-2025-04-14’s answer.
  1. 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; }

    왜??

  2. 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 방식으로 수정된 정답 코드도 드릴 수 있어요!


Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.