글 읽기 - 반례를 못 찾겠습니다.

banana970 1년 전 0

다 잘한 거 같은데... '틀렸습니다'가 나오네요.

반례가 있을까요? 혹은 틀린 이유를 알 수 있을까요?

#include <iostream>
#include <queue>
#include <cstring>
#include<string>
#include <utility>


using namespace std;

int visit[10001] = {};

void BFS(int A, int B, string s) {
	queue <pair<int,string>> q;
	int T1, T2, T3;
	q.push(make_pair(A, s));
	while (!q.empty()) {
		int front = q.front().first;
		string str = q.front().second;
		if (front == B) { cout << str; break; }
		q.pop();
		T1 = front * 2 % 10000;
		if (visit[T1] == 0) {
			visit[T1] = 1;
			q.push(make_pair(T1, str + 'D'));
		}
		if (front == 0 && visit[9999] == 0) {
			visit[9999] = 1;
			q.push(make_pair(9999,str+'S'));
		}
		else if (front!=0&&visit[front - 1] == 0) {
			visit[front - 1] = 1;
			q.push(make_pair(front - 1,str+'S'));
		}
		int k = front / 1000;
		T2 = (front % 1000) * 10;
		if (visit[T2 + k] == 0) {
			visit[T2 + k] = 1;
			q.push(make_pair(T2 + k,str+'L'));
		}
		k = front % 10;
		T3 = front / 10 + 1000*k;
		if (visit[T3] == 0) {
			visit[T3] = 1;
			q.push(make_pair(T3, str + 'R'));
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int T, A, B;
	string s;
	cin >> T;
	for (int i = 0; i < T; i++) {
		s="";
		cin >> A >> B;
		visit[A] = 1;
		BFS(A, B, s);
		memset(visit, 0, 10001);
		cout << '\n';
	}
}

wnwoghd22 1년 전 0

로직이 틀린 건 아닙니다.

memset의 사용법이 잘못되어서 그렇습니다.

memset의 세번째 인자는 배열의 전체 바이트 크기를 받아야 하는데, 이는 [배열 길이] * (자료형 크기)입니다.

자세한 컴파일 환경을 모르지만, 보통 int의 크기는 8byte 정도로, 10001을 인자로 넘겨서는 제대로 초기화가 되지 않습니다.

세번째 인자를 다음과 같이 바꾸시면 됩니다:

memset(visit, 0, 10001 * sizeof(int));
memset(visit, 0, sizeof visit);

/** 또는 **/

bool visit[10001] = {}; // bool 자료형은 1byte -> 위 로직은 visit에 0 또는 1만 넣기 때문에 bool로 바꿔도 무방함
memset(visit, 0, 10001);

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

문제

문제

출처

ICPC

반례를 못 찾겠습니다.

banana970 1년 전 0

wnwoghd22 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말