글 읽기 - 예외 테케를 못찾겠습니다 ㅜㅜ

uk7880 4년 전 0

도움을 주시면 감사하겠습니다!

시작 2진수와 도착 2진수를 10진수로 변환하여 BFS를 돌렸습니다.

자꾸 틀렸습니다.가 떠서 어떤 테스트케이스를 통과하지 못하는지 못찾겠습니다..ㅠㅠ

#ifdef _DEBUG
#include "bits_stdc++.h"
#else
#include "bits/stdc++.h"
#endif
#pragma warning(disable:4996)
using namespace std;
char l[12];
bool visit[(1 << 10)+1];
int s, d, sod[12];
int main() {
#ifdef _CONSOLE 
	freopen("sample.txt", "r", stdin);
#endif
	for (int i = 0; i < 12; i++) sod[i+1] = (1 << i);

	//시작 이진수를 10진수로
	scanf("%s", l);
	for (int i = strlen(l) - 1,tmp=1; i >= 0; i--, tmp <<= 1) s += (l[i] - '0')*tmp;

	//도착 이진수를 10진수로
	scanf(" %s", l);
	for (int i = strlen(l) - 1, tmp = 1; i >= 0; i--, tmp <<= 1) d += (l[i] - '0')*tmp;
	queue<pair<int, int> > q;
    // first : 현재 좌표
    // second : 현재 좌표까지의 count
	q.push({ s,0 });
	visit[s] = true;

	while (!q.empty()) {
		auto outdata = q.front();
		q.pop();
		if (outdata.first == d) {
			printf("%d\n", outdata.second);
			break;
		}
		//0부터
		if (outdata.first - 1 >= 0 && !visit[outdata.first - 1]) {
			visit[outdata.first - 1] = true;
			q.push({ outdata.first - 1,outdata.second + 1 });
		}
		//최대 1023까지
		if (outdata.first + 1 < 1024 && !visit[outdata.first + 1]) {
			visit[outdata.first + 1] = true;
			q.push({ outdata.first + 1,outdata.second + 1 });
		}

		int idx;
        // 맨앞비트 값 구하기 ex) 1001(2) 이면 sod[idx]=1000(2)=8
		for (idx = 10; idx >= 0 && sod[idx]>outdata.first; idx--){} 

		// 초기 : 위에서 구한 값에서 /2
        // 0이 될때까지 /2
		for (idx = idx - 1; idx >= 0; idx--) {
            // 맨 앞을 제외한 비트들 반전
			int tmp = (outdata.first ^ sod[idx]);
			if (!visit[tmp]){
				visit[tmp] = true;
				q.push({ tmp,outdata.second + 1 });
			}
		}
	}
}

pichulia 4년 전 1

sod배열을 12개까지 잡으시고 sod[12]에 접근해서 생긴 문제입니다.

uk7880 4년 전 0

와.. 정말.. 항상 바보같은 곳에서 실수하니까 그저 공허하네요.....

일단 해결은 했습니다. 도움을 주신 pichulia님 감사합니다.

그런데 추가적으로 궁금한게 있습니다.

12에 접근하게 되면 런타임 에러가 떠야하지않나요??

틀렸습니다.가 뜬 이유가 궁금합니다...

ryute 4년 전 1

12번 인덱스에 접근하는 것은 올바르지 않은 행동이기 때문에, 어떤 결과가 일어나더라도 아무것도 보장된 것이 없기에 이상할 것이 없습니다. 틀렸습니다가 아니라 시간 초과가 나도, 출력 초과가 나도, 메모리 초과가 나도 정상입니다.

uk7880 4년 전 0

선언하지 않은 인덱스에 접근 시 런타임 에러가 보장 되는 줄 알았습니다.

한 가지 더 배워갑니다^^..

답변 주신 ryute님 감사합니다!

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

문제

문제

출처

ICPC

예외 테케를 못찾겠습니다 ㅜㅜ

uk7880 4년 전 0

pichulia 4년 전 1

uk7880 4년 전 0

ryute 4년 전 1

uk7880 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말