3-H_13913 숨바꼭질4

작성한 질문수 25

1

안녕하세요 효민님 ㅎㅎ

제 생각에 효민님은 흔적의 정점들을 vector에다가 담고 그 담은 것 중에서 답인 것을 추출해내는 것으로 생각한 것 같은데요.

			cnt[there]=cnt[here]+1;
			v[there]=v[here];
			v[there].push_back(there);

근데 여기서 이렇게가 아니라.

			v[there].push_back(here);

이런 꼴이 되어야 하지 않을까요?

또한 런타임 에러는 다음 부분에서 발생이 됩니다.

			if(cnt[there] || there>=max_ || there<0) continue;

자 만약 there이 -1일 때 cnt[-1]로 참조할 것 같지 않나요?

우리는 배열을 쓸 때 인덱스가 음수인지 오버플로인지 항상 체크해야 합니다.

즉,

			if(there>=max_ || there<0 || cnt[there]) continue;

이렇게 하셔야 합니다.

다듬은 코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;
int n,k;
int cnt[200004];
vector<int> v[200004];
int max_=200004;

int main(){
	
	cin >> n >> k;
	
	queue<int> q;
	q.push(n);
	cnt[n]=1;
	v[n].push_back(-1);
	
	while (true){
				
		int here = q.front(); q.pop();
		if(here==k) break;
		
		for(int there: {here+1, here-1, here*2}){
			if(there>=max_ || there<0 || cnt[there]) continue;
			
			q.push(there);
			cnt[there]=cnt[here]+1; 
			v[there].push_back(here);
		}
		
		
		
	}
	
	cout << cnt[k]-1 << "\n";
	vector<int> ret; 
	while(k != -1){ 
	    ret.push_back(k);
	    k = v[k][0]; 
	}   
	reverse(ret.begin(), ret.end());
	for(int i : ret) cout << i << "\n";
	return 0;
} 

이걸 의도하신거죠? ㅎㅎ

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.