papayetoo   1년 전

다른 질문에서의 반례들 모두 문제 없이 돌아가는 데 제 코드에 잘못된 점이나 통과 안되는 반례가 있는 지 알려주시면 감사하겠습니다.

djm03178   1년 전

97번째 줄이 없어야 합니다.

papayetoo   1년 전

system("pause");

지운 후에 다시 돌려도 여전히 오류가 납니다. 

뭐가 문제점인지 짐작이 안갑니다. 다른 수정한 코드에서는 sort 이용한 후 제출했는 데도 여전히 틀림이네요.

아래 코드가 수정된 부분입니다.

        pair* edges = new pair[m];
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		edges[i] = pair(a, b);
	}
	sort(edges, edges + m, pair_compare);
	for (int i = 0; i < m; i++) {
		int first = edges[i].first;
		int second = edges[i].second;
		adj_node[first]->addNode(second);
		adj_node[second]->addNode(first);
	}
    dfs(start_node, dfs_visited, adj_node);
    cout << "\n";
    bfs(start_node, bfs_visited, adj_node);

djm03178   1년 전

이렇게 부분적으로 올리지 마시고 수정된 전체 코드를 다시 올려주시는 게 좋습니다. 정말로 저것만 바꾸면 컴파일조차 안 돼서 테스트를 할 수가 없습니다.

papayetoo   1년 전

죄송합니다 생각이 짧았습니다. 수정본 전체 올렸습니다.

예상되는 문제는

Input :

4 5 1

1 4

1 3

1 2

2 4

3 4

예제와 같이 답이 안 나올까봐 별도의 sort를 썼는데 output은 정상으로 나오는데 다른 문제가 뭔지 상상이 안 됩니다.

pichulia   1년 전

addNode 함수 내부가 잘못됐습니다.

기껏 temp->getData() > index 를 만족하도록 temp값을 구해놨는데

temp의 next가 n이 되버립니다.

papayetoo   1년 전

pichulia님

코드 수정하지 않고 돌려도 아래처럼 나오는데 맞지 않나요?

pichulia   1년 전

어우;; 반례 만들기 힘들게 왜 edge는 정렬하셨나요 -_-;;


제가 쓴 댓글을 보시면 반례가 없어도 어디가 잘못됐는지.. 아니 어디가 잘못됐는지 아얘 대놓고 알려줬는데

굳이 반례가 필요할까 싶긴한데... 굳이굳이굳이 반례를 원하신다면야.;;

일단 랜덤데이터로 반례 만들어보고있을테니까


addNode 함수 구현이 잘못됐다는 제 피드백을 확인해보고 계세요

pichulia   1년 전

여기 반례 드리겠습니다. 위쪽 2개가 정답이고, 아래쪽 2개가 게시판에 올리신 코드가 출력하는 내용입니다. 사실 5개 다 똑같은 그래프에 시작점만 달라진건데..각각이 다 의미가 ㅣㅇㅆ을거같아서 걍 다 첨부했습니다.


...그리고...그리고... addNode에서 추가된

Node* n = new Node(index); 이 친구들을 delete 해주지 않아서 메모리누수가 생겨서 제 컴퓨터가 죽었습니다 -_-;;

이 문제를 푸는 것과는 직접적인 연관관계는 없지만
앞으로 프로그래밍을 계속 하실 예정이라면 이 부분도 신경쓰시길 바랍니다.아래 코드는 "소멸자"라는 녀석입니다.


~Node(){
  if(next) {
    delete next;
  }
}


papayetoo   1년 전

addNode 부분 해결했습니다. 저는 pair<int, int>를 sort해서 넣으면 별다른 문제가 생기지 않을 거라고 생각했는데 문제가 그렇게 호락호락 풀리지는 않았네요.

동적 할당 부분에 대해서 garbage collection을 해야한다고 생각은 하고 있었는데 저렇게 간단히 해결할 줄은 몰랐습니다;;

실례가 안된다면 c++ 관련해서 stackoverflow나 구글에서 다른 개발자 분들 보면 일반 포인터 말고 스마트 포인터를 사용하라고 하는 데, 이 문제에서도 스마트 포인터를 이용할 수 있을 까요? unique_ptr, weak_ptr 등 개념은 알고 있지만 정확히 언제 써야하는지는 통 감이 오지 않습니다.

 

댓글을 작성하려면 로그인해야 합니다.