inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

2-S fill과 memset 질문 있습니다.

해결된 질문

279

찬비

작성한 질문수 18

1

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;



int n, m, a, b;
int _max = numeric_limits<int>::min();
int virus[10002];
vector<int> adjList[10002];
bool visited[10002];

void fastIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int DFS(int v) {
    visited[v] = 1;
    int infection = 1;
    for (auto adjV : adjList[v]) {
        if (visited[adjV]) continue;
        infection += DFS(adjV);
    }
    return infection;
}

int main() {
    fastIO();

    cin >> n >> m;
    while (m--) {
        cin >> a >> b;
        adjList[b].push_back(a);
    }

    for (int i = 1; i <= n; i++) {
        //memset(visited, 0, sizeof(visited));
        fill(visited, visited + 10000, 0);
        virus[i] = DFS(i);
        _max = max(_max, virus[i]);
    }

    for (int i = 1; i <= n; i++) {
        if (virus[i] == _max) {
            cout << i << ' ';
        }
    }

    return EXIT_SUCCESS;
}

완탐을 DFS로 변경하여 풀었는데, fill()을 사용하여 0으로 초기화하면 계속 틀렸다 채점돼서 풀이 참고하여 memset()으로 변경하니 정답으로 채점됩니다.

똑같이 0으로 초기화 하는 것 아닌가요..?

코테 준비 같이 해요! C++

답변 2

2

찬비

visited[10000] 까지 초기화 하려면 visited + 10001이라고 했어야 했는데 실수 했네요.

해결했습니다. 비슷한 실수 하시는 분들 있을까봐 참고하라고 그냥 두겠습니다.

1

큰돌

안녕하세요. 찬비님ㅎㅎ

fill 함수의 내부 구현체를 보면 다음과 같이 되어있습니다.

template <class ForwardIterator, class T>

  void fill (ForwardIterator first, ForwardIterator last, const T& val)

{

  while (first != last) {

    *first = val;

    ++first;

  }

 

}

 

Forward iterators to the initial and final positions in a sequence of elements that support being assigned a value of type T. The range filled is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.

또한 지금 보시면 범위를 [first,last) 로잡아야 한다고 되어있구요. 

이렇기 때문에 만약 10002로 잡았다면 visited + 10002가 되어야 합니다. 

또 질문사항있으시면 언제든 말씀 부탁드립니다. 

감사합니다. 

 

강사 큰돌 올림.

 

 

1-E질문입니다!

0

518

2

3-L 틀린 부분 피드백 부탁드립니다.

0

820

2

1-A문제 순열재귀함수 질문입니다.

0

381

1

1-A 일곱난쟁이문제입니다

0

456

1

문제 풀 때 방향성에 대해

0

800

1

맥에서 vs code로 실행 관련 질문입니다

0

523

1

17071번 메모리 초과

0

386

1

1-C질문입니다!

0

421

2

2-B BFS 시간초과질문

0

630

2

1-O 13번 라인

0

441

1

6-J 놀이공원 문제 질문

0

381

1

구현관련 질문

0

483

1

강의 교안

0

319

1

실력을 더 올리고나서 강의를 보는 것이 맞을까요?

0

545

1

안녕하세요! 재귀함수에 관해서 질문드립니다

0

535

1

1-K

0

473

2

3-G번 질문있습니다.

1

473

3

3-C 실행 시간 질문드립니다.

0

493

1

4-A 문제 풀이 질문있습니다.

0

590

2

비트마스킹 연산자 "1의 보수" 영문 표기법

0

435

1

격자탐색 문제에서 BFS 시간복잡도 질문드립니다.

0

334

1

3-O go 함수 질문 드립니다.

1

447

2

4-A 출력 질문

0

304

1

1주차 1-O 질문드립니다

0

258

1