글 읽기 - 채점에 오류가 있는 것 같습니다.

robbyra98 3년 전 0

제가 작성한 코드인데, test case 1 제외하고는 돌려보면 결과가 다 다른데, 채점 서버에서는 맞았다고 뜨네요.

참고로 저는 VS 컴파일러를 사용하고 있습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

bool visited[1001];

void dfs(int **adj, int vertex, int size) {
	cout << vertex << " ";
	visited[vertex] = true;
	for (int i = 1; i <= size; i++) {
		if (adj[vertex][i] && !visited[i]) {
			dfs(adj, i, size);
		}
	}
}

void bfs(int **adj, int vertex, int size, queue<int> q) {
	visited[vertex] = true;
	q.push(vertex);

	while (!q.empty()) {
		vertex = q.front();
		q.pop();
		cout << vertex << " ";
		for (int i = 1; i <= size; i++) {
			if (adj[vertex][i] && !visited[i]) {
				q.push(i);
				visited[i] = true;
			}
		}
	}
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int N, M, V;

	cin >> N >> M >> V;

	queue<int> q;


	int **adj;
	adj = new int *[N + 1];
	for (int i = 0; i <= N; i++) {
		adj[i] = new int[N + 1];
	}

	memset(adj, 0, sizeof(adj));
	memset(visited, false, sizeof(visited));


	while (M--) {
		int v1, v2;
		cin >> v1 >> v2;
		adj[v1][v2] = 1;
		adj[v2][v1] = 1;
	}

	dfs(adj, V, N);
	cout << '\n';
	
	memset(visited, false, sizeof(visited));
	memset(adj, 0, sizeof(adj));
	bfs(adj, V, N, q);

	delete[] adj;
}

djm03178 3년 전 0

환경마다 결과가 다르게 나올 수 있습니다. Undefined behavior가 있다면 그렇게 됩니다. 이것 때문에 채점 환경에서 맞게 나온 걸 맞게 채점했다고 해서 채점에 문제가 있다고 할 수 없습니다.

그러한 부분이 없는 것을 정말 확신할 수 있으신가요? 그렇지 않다면 채점에 문제가 있다고 판단할 수 없습니다.

robbyra98 3년 전 0

g++ 컴파일러 상에서는 정상 동작하네요. 제 코드에서 미정의 동작을 발견하지는 못했는데, 이유가 뭘까요?

54, 69번째 줄은 adj에 동적할당된 메모리를 전부 0으로 초기화하는 문장이 아닙니다. sizeof(adj)는 int **의 크기, 즉, 채점 서버에서는 8이고, adj는 이중 포인터이므로 이 크기만큼을 0으로 초기화하는 것은 곧 adj[0]에 0을 대입하는 문장과 같습니다. 물론 이 코드에서 이후 0번 인덱스를 건드리지는 않지만, 결국 초기화가 안 됐기 때문에 실제 간선 정보를 나타내는 부분들에 어떤 값이 들어있을지 알 수 없는 상태가 되고, 초기화되지 않은 변수를 사용하는 것이 바로 undefined behavior입니다.

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

문제

문제

출처

ICPC

채점에 오류가 있는 것 같습니다.

robbyra98 3년 전 0

djm03178 3년 전 0

robbyra98 3년 전 0

djm03178 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말