글 읽기 - c++ 왜 틀렸는지 모르겠습니다.ㅜㅜ

celestial 3년 전 0

일단 mintime이라는 배열을 선언하여

방문을 한 지점이라 할 지라도 최솟값이 발생하면 계속하여 갱신을 하도록 진행하였습니다.

이 부분을 계속 세 군데에나 걸리게 해두었는데...

어쨋건 모든 bfs를 돌도록 한 다음 동생의 위치 K에서의

mintime[K]를 출력하도록 했는데 계속 틀립니다ㅜㅜ!!

그리고 디버깅을 하는 과정에서

mintime[i]>nexttime 이면 mintime[i]=nexttime을 해주는데

mintime[i]가 nexttime으로 갱신되었음에도 불구하고 값이 자꾸 변화하는 경우가 생깁니다;;;

이런 경우 어떻게 해야 할지 도움주시면 정말 감사합니다!!ㅜㅜ

앗 참고!!!!! 지금 혹시 몰라서 아래 소스코드를 돌렸는데 그냥 답이 맞습니다!!

그런데 문제는 예제의 답인 5 17을 돌려보면 1이 출력된다는 점입니다;;;;;;;;;;;;;

그거때문에 맞아도 맞은 것 같지 않은 느낌이 계속 드네요...어떻게 된 일일까요?ㅜㅜㅜ

#include<iostream>
#include<vector>
#include<stdio.h>
#include<queue>
#define MAX 100001
using namespace std;



int map[MAX];
int mintime[MAX];
bool visited[MAX];
int dx[3] = { 1,-1,2 };

typedef struct node {

	int x;
	int time;


	node(int a, int b) {
		x = a;
		time = b;
	}
};


int N, K;
int ans;
queue<node> Q;



void BFS() {


	node current(1, 0);

	while (!Q.empty()) {

		current.x = Q.front().x;
		current.time = Q.front().time;
		Q.pop();

		if (current.x == K) {
			//printf("<<<<<<<<<<<<<<<<<<<<<<<<답을 찾았습니다!!>>>>>>>>>>>>>>>>>>>>>>>>>>>\n\n");
			if (mintime[current.x] > current.time) {
				//printf("mintime[current.x] : %d current.time : %d \n\n", current.x, current.time);
				mintime[current.x] = current.time;
			}
			
			
			//printf("최솟값 : %d \n\n", mintime[current.x]);
			
		}

		for (int i = 0; i < 3; i++) {

			int next = dx[i];

			if (next != 2) {

				int x = current.x + dx[i];
				int nexttime = current.time + 1;
				

				if (visited[x] && mintime[x] > nexttime) {
					//printf("방문하였으나 최솟값 갱신이 필요합니다. mintime[x] : %d nexttime : %d \n\n", mintime[x], nexttime);
					mintime[x] = nexttime;
					
					Q.push(node(x, nexttime));
				}

				if (!visited[x] && 0 <= x && x <= MAX) {
					visited[x] = true;
					mintime[x] = nexttime;
					//printf("next x : %d next mintime : %d \n\n", x, mintime[x]);
					Q.push(node(x,nexttime));


				}
				else {
					continue;
				}

			}

			else {
				int x = current.x * dx[i];
				int nexttime = current.time;

				if (visited[x] && mintime[x] > nexttime) {
					//printf("방문하였으나 최솟값 갱신이 필요합니다. mintime[x] : %d nexttime : %d \n\n", mintime[x], nexttime);
					mintime[x] = nexttime;
					
					Q.push(node(x, nexttime));
				}


				if (!visited[x] && 0 <= x && x <= MAX) {
					visited[x] = true;
					mintime[x] = nexttime;
					//printf("next x : %d next mintime : %d \n\n", x, mintime[x]);
					Q.push(node(x,nexttime));


				}
				else {
					continue;
				}




			}
				
		}

	}
}


int main() {

	cin >> N >> K;

	visited[N] = true;
	
	
	for (int i = 0; i <= MAX; i++) {
		mintime[i] = 10000;
	}
	
	mintime[N] = 0;
	Q.push(node(N, 0));
	BFS();
	ans = mintime[K];
	printf("%d", ans);


}

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