3-H 질문합니다.

작성한 질문수 2

1

안녕하세요 현빈님 ㅎㅎ

MAP을 사용한 것은 상관이 없구요.

이 코드때문에 그렇습니다.

void bfs(int here) {
	
	queue<int> q;
	q.push(here);
	visited[here] =1;
	mp[here] = 0;	
	mp[0] = MAX+1;
	while(q.size()) {
		int here = q.front();
		q.pop();
		for(int there : {here+1, here-1, here*2}) {			
			if(there < 0 || there > MAX) continue;		

이 부분이요. there은 max까지 들어갈 수 있겠죠?

visited를 배열을 4 크기로 만들어놨을 때 0, 1, 2, 3 까지 인덱스가 참조가 가능한데

이 코드는. max 초과 일 때만 continue이기 때문에

visited 의 max가 4일 때 4 인덱스를 참조를 할 수 있게 됩니다.

따라서

void bfs(int here) {
	
	queue<int> q;
	q.push(here);
	visited[here] =1;
	mp[here] = 0;	
	mp[0] = MAX+1;
	while(q.size()) {
		int here = q.front();
		q.pop();
		for(int there : {here+1, here-1, here*2}) {			
			if(there < 0 || there >= MAX) continue;	

이렇게 해주셔야 합니다.

또한, 현빈님 코드에는 불필요한 부분들이 많습니다.

한번 정리해볼까요?

굳이 0일 경우 나눌 필요가 없었고, 필요없는 배열이나 변수 등을 제거해봤습니다.

#include<bits/stdc++.h>
using namespace std;

int n,k;
const int MAX = 200004;
int visited[MAX]; 
map<int,int> mp;

void bfs(int here) {
	
	queue<int> q;
	q.push(here);
	visited[here] = 1; 
	while(q.size()) {
		int here = q.front();
		if(here == k) break;
		q.pop();
		
		for(int there : {here+1, here-1, here*2}) {			
			if(there < 0 || there >= MAX) continue;			
			if(visited[there]) continue; 
		
			visited[there] = visited[here]+1;					
			mp[there] = here;	 
			q.push(there);
		}
	}
	return;
}


int main() {
    cin >> n >> k;  
    bfs(n); 
    vector<int> v;   
    for(int i = k; i != n; i = mp[i]){
        v.push_back(i);
    }  
    v.push_back(n);
    cout << v.size() - 1 << "\n";
    for(int i = v.size() - 1; i >= 0; i--){
        cout << v[i] << " ";
    }  
    return 0;
}

이렇게 좀 더 깔끔하게 짜면 더 좋은 코드가 될 거 같습니다.

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

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

감사합니다.

강사 큰돌 올림.