글 읽기 - 반례를 찾습니다. BFS 및 백트래킹 질문입니다.

adfsfsf 5년 전 0

잘못된 부분이 있다면 k>n인 부분에서 있을 것 같습니다.

#include <iostream>
using namespace std;
long int n, k, co, t1[500000], t2[500000], t2i, i, p[500000];
int main(void)
{
	cin >> n >> k;
	if (k < n)//동생이 수빈이보다 작은 위치에 있을 때에는 거리의 차(순간이동은 큰 수로만 이동)
		cout << n - k << endl;
	else if (k == n)//서로 같으면 0 출력
		cout << "0" << endl;
	else//이외의 경우 백트래킹 + BFS
	{
		t1[0] = k;
		t1[1] = -1;
		p[k] = 1;//같은 점 중복 방문 방지(시간 단축)
		while (1)//루프가 시작될 때마다
		{
			co++;//1초 증가
			i = 0;
			while (1)
			{
				if (t1[i] == -1)//유효한 점을 탐색하지 않을 경우 루프 탈출
					break;
				if (p[t1[i] - 1] == 0)//(조사 중인 점 - 1)이 확인 안 한 점이면
				{
					t2[t2i] = t1[i] - 1;//다음 회차 확인 목록에 추가
					t2i++;
					p[t1[i] - 1] = 1;//해당 점을 추가했음을 표시
					if (t1[i] - 1 == n)//만약 해당 점이 n이면
					{
						cout << co << endl;//체크 횟수 출력
						return 0;
					}
				}
				if (t1[i] + 1 < k * 2)//k*2를 넘어가면 의미가 없음(순간이동은 * 2)
				{
					if (p[t1[i] + 1] == 0)//확인 여부 체크
					{
						if (t1[i] + 1 == n)//n이면 횟수 출력 후 종료
						{
							cout << co << endl;
							return 0;
						}
						t2[t2i] = t1[i] + 1;
						t2i++;
						p[t1[i] + 1] = 1;
					}
				}
				if (t1[i] % 2 == 0)//짝수인 점이면
				{
					if (p[t1[i] / 2] == 0)//점의 절반 위치를 체크
					{
						if (t1[i] / 2 == n)//절반 위치가 n이면 횟수 출력
						{
							cout << co << endl;
							return 0;
						}
						t2[t2i] = t1[i] / 2;
						t2i++;
						p[t1[i] / 2] = 1;
					}
				}
				i++;
			}
			for (i = 0; i < t2i; i++)//t1으로 t2의 값들 옮김
				t1[i] = t2[i];
			t1[i] = -1;//마지막 칸에 -1을 넣어 유효 여부 표시
			t2i = 0;
		}
	}
	return 0;
}

adfsfsf 5년 전 0

찾았습니다. 24번 줄에서 t1[i]가 0보다 클 때만 -1을 허용해야 하는데 그러지 않아서 배열 밖을 탐색해서 생긴 문제였습니다.

https://www.acmicpc.net/board/... 이 페이지가 도움이 되었습니다.

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

문제

문제

출처

ICPC

반례를 찾습니다. BFS 및 백트래킹 질문입니다.

adfsfsf 5년 전 0

adfsfsf 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말