2-S (1325번 - 효율적인 해킹) 문제 질문 드립니다.

9 asked

0

안녕하세요 찬영님 ㅎㅎ

이부분이요.

	for (int i = 1; i <= n; i++) {
		memset(visited, 0, sizeof(visited));
		cnt = 0; //초기화
		visited[i] = 1;
		DFS(i);```

이렇게 visited를 걸고 dfs를 돌려야 하는게 아닐까요?

왜그러냐면,

DFS 함수를 보면 dfs함수를 호출하면서 해당 정점으로부터 이어진 정점에 대해 VISITED를 하고 DFS를 하고 있죠?

void DFS(int here) {
	cnt++; //풀이에서는 ret을 축척하는 걸로 하고 있다. 
	for (auto it : v[here]){
		if (visited[it] == 0){
			visited[it] = 1;
			DFS(it);

그렇기 때문에 시작정점 또한 visited를 처리하고 dfs를 돌려주어야 합니다.

안 그러면 시작정점 방문 처리가 안되어 "다시 불필요하게 방문"하게 되는 문제가 발생이 됩니다.

우리가 생각했던 로직과 다르기 때문에 UB가 발생하고 그로인해 출력초과가 발생하는 것 같아요.

또한,

시간초과가 만약 난다면 ios를 다음과 같이 넣어보세요.

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;

http://boj.kr/b2022eed54ff47a3a60f654f8904232c

해당 링크 또한 참고해주세요. :)

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

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

감사합니다.

강사 큰돌 올림.