글 읽기 - 53퍼센트에서 틀렸습니다가 나옵니다!

fantasy7772 2년 전 0

visited배열에 그 위치에 도달하기 전 위치를 저장하는 방식으로 경로를 찾았고 게시판에 나오는 케이스들도 다 맞는 것 같습니다ㅠㅠ 하지만 53퍼센트에서 틀렸습니다가 나오는데 어느 부분에서 잘못되었는지 잘 모르겠습니다..

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <cmath>
#include <queue>
#include <cstring>
#include <string>
#include <deque>
#include <tuple>
#include <set>
using namespace std;
//const int INF = 0x3f3f3f3f;
int visited[100001] = { 0, };
queue<pair<int, int>> q;
int A, B;
int cnt = 0;
bool isin(int loc) {
	if (loc >= 0 && loc <= 100000) {
		return true;
	}
	return false;
}
void BFS() {
	while (!q.empty()) {
		int cur_loc = q.front().first;
		int cur_cnt = q.front().second;
		q.pop();
		if (cur_loc + 1 == B || cur_loc - 1 == B || cur_loc * 2 == B) {
			cout << cur_cnt + 1 << endl;
			visited[B] = cur_loc;//목적지 도달하기 전 위치
			cnt = cur_cnt+1; //총 경로의 개수 저장
			return;
		}

		if (isin(cur_loc + 1) == true) {
			if (visited[cur_loc + 1] == 0) {
				visited[cur_loc + 1] = cur_loc; //다음 위치 전 위치 저장
				q.push(make_pair(cur_loc + 1, cur_cnt + 1));
			}
		}

		if (isin(cur_loc - 1) == true) {
			if (visited[cur_loc - 1] == 0) {
				visited[cur_loc - 1] = cur_loc;
				q.push(make_pair(cur_loc - 1, cur_cnt + 1));
			}
		}

		if (isin(cur_loc * 2) == true) {
			if (visited[cur_loc * 2] == 0) {
				visited[cur_loc * 2] = cur_loc;
				q.push(make_pair(cur_loc * 2, cur_cnt + 1));
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> A >> B;
	if (A == B) {
		cout<< 0 <<endl;
		cout << A << endl;
		return 0;
	}
	stack<int> st;
	q.push(make_pair(A, 0));
	BFS();
	int track = B;
	st.push(B);
	for (int i = 0; i < cnt; i++) {//경로 찾는 과정
		st.push(visited[track]);
		track = visited[track];
	}
	while (!st.empty()) {
		cout << st.top() << " ";
		st.pop();
	}
}

fantasy7772 2년 전 0

제가 좌표 0을 생각안하고 visited배열을 0으로 초기화 시킨것이 문제였습니다!

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

문제

문제

출처

ICPC

53퍼센트에서 틀렸습니다가 나옵니다!

fantasy7772 2년 전 0

fantasy7772 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말