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

안녕하세요 너무님 ㅎㅎ

솔직히 거의 99%는 잘 짜셨고,

작은 차이밖에 없는 것 같은데 불필요한 로직을 없애보고자했습니다.

로직을 보면

  for(int i = 0; i < vec[idx].size(); i++){
    if(visited[vec[idx][i]] == 0){
      visited[vec[idx][i]] = 1;
      cnt++;
      recur(vec[idx][i]);

방문처리 -> recur를 하고 있습니다.

근데 첫방문지점의 경우 이렇게 안하고 있더군요. 이렇게 되면 처음 지점에 대한 방문이 2번 일어나게 될 수도 있습니다. 따라서 이런식으로 수정해야 합니다.

  for(int i = 1; i <= n; i++){ 
    memset(visited, 0, sizeof(visited));
    cnt = 1;
    visited[i] = 1;
    recur(i);

사소하지만 이 때문에 통과가 안되는 것 같습니다.

저도 여러번 시도하며 고쳐봤고. 이제는 통과가 됩니다.

전체코드

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

int n, m;
int a, b;
int cnt = 0;
vector<int>vec[10004];
int hacking[10004];
int visited[10004];

void recur(int idx){ 
  if(vec[idx].size() == 0)
    return;
  for(int i = 0; i < vec[idx].size(); i++){
    if(visited[vec[idx][i]] == 0){
      visited[vec[idx][i]] = 1;
      cnt++;
      recur(vec[idx][i]);
    }
  }
}
int main(){
  ios_base::sync_with_stdio(false); 
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> m;
  for(int i = 0; i < m; i++){
    cin >> a >> b;
    vec[b].push_back(a);
  }
  for(int i = 1; i <= n; i++){ 
    memset(visited, 0, sizeof(visited));
    cnt = 1;
    visited[i] = 1;
    recur(i);
    hacking[i] = cnt;
  }

  int maximum = *max_element(hacking, hacking+10004);
  for(int i = 1; i <= n; i++){
    if(hacking[i] == maximum)
      cout << i << " ";
  } 
  
  return 0;
}

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

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

감사합니다.

강사 큰돌 올림.