인프런 커뮤니티 질문&답변

안녕하세요 기태님 ㅎㅎ

전반적으로 잘 짜셨습니다.

다만,

이 문제를 보시면 1번부터시작이 됩니다.0번부터가 아닙니다. 이 부분 수정 + 카운팅 부분은 분리하지 않고 같이 할 수 있습니다.

제가 한번 다듬어봤는데요. ㅎㅎ 참고부탁드립니다.

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[10004];
int visited[10004];
int nr_hacked[10004];
int N, M, max_hacked = -1;
vector<int> res_best_hacker;

int cnt_hacked;

void go(int from) {
    visited[from] = 1;
    cnt_hacked++;
    for(auto i: adj[from]) {
        if(!visited[i]) {
            go(i);
        }
    }
}

int main() {
    int from_temp, to_temp;
    cin >> N >> M;
    
    for(int i = 0; i < M; i++) {
        cin >> to_temp >> from_temp;
        adj[from_temp].push_back(to_temp);
    }

    for(int i = 1; i <= N; i++) {
        cnt_hacked = 0;
        fill(visited, visited + N + 1, 0);
        go(i);
        nr_hacked[i] = cnt_hacked;
        
        if(nr_hacked[i] > max_hacked) {
            max_hacked = nr_hacked[i];
        }
    }

    for(int i = 1; i <= N; i++) {
        if(nr_hacked[i] == max_hacked) {
            cout << i << " ";
        }
    }

    return 0;
}

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI 인턴입니다. Gitae Kim님.

주어진 문제는 대개 그래프 탐색 문제로, 각 정점을 시작으로 하여 가능한 최대 해킹 수를 찾는 것이 목표입니다. 여기서는 기본적으로 DFS(깊이 우선 탐색)를 활용하여 해킹 가능한 컴퓨터의 수를 세는 방식입니다.

Gitae Kim님께서 작성하신 코드는 예제를 통과하지만 채점에서 오답이 나오고 있다 하셨는데요, 이를 해결하는 주요 방법 중 하나는 시간 복잡도를 줄이거나, 잘못된 변수 초기화 및 조건 검사를 확인하는 것입니다.

참고 답변 및 자료:

1. 유사한 질문과 해결 방법: 2-S 1325 질문입니다.

   • 이 답변에서는 중복된 DFS 호출과 불필요한 방문 처리로 인한 시간 초과 문제를 해결하는 방법을 설명합니다. 특히, if 조건 내에서 두 번의 dfs 호출이 이루어지는 부분이 문제가 되었던 사례를 다루며, 이런 부분이 없나 확인해 보시면 좋을 것 같습니다.
     

2. 다른 질문 및 진단 방법: 2-S 효율적인 해킹 문제 (중간에 값이 변합니다 ㅠㅠ)

   • 변수 초기화 문제 및 반복문 사용 시 불필요한 계산을 방지하는 방법을 검토할 수 있습니다.
     

3. 효율적인 탐색 최적화: 코드의 논리 구조가 맞다면, 시간 복잡도를 최적화하기 위해 ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);를 사용해 입출력 성능을 향상시킬 수 있습니다.

위의 답변들을 참고하시면 문제의 원인을 파악하는 데 도움이 되실 것입니다. 주로 발생하는 문제는 중복된 계산이나 방문 처리의 오류, 혹은 변수 및 메모리 관련 사소한 버그일 수 있습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.