글 읽기 - 1697번 맞았는데 약간 이해가 안되는 부분이 있어서 질문합니다.

chaeaok 4년 전 2

이게 틀린 코드고 댓글이 맞은 코드인데 왜 visited랑 num_n 범위를 늘려줘서 정답이 된거죠

제가 생각해봤을때는 상관 없을 거 같은데 두개의 채점결과가 달라서 질문드립니다.

#include <iostream>
#include <queue>
#include <utility>
#include <cmath>
using namespace std;

bool End = false;
bool visited[100001];
int cnt = 0;

void bfs(int a, int b) {
	queue<pair<int,int>> q;
	q.push({ a, cnt });
	visited[a] = true;
	while (End == false) {
		int num = q.front().first;
		cnt = q.front().second;
		q.pop();
		visited[num] = true;
		for (int i = 0; i < 3; i++) {
			int num_n;
			if (i == 0) num_n = num * 2;
			else if (i == 1) num_n = num - 1;
			else num_n = num + 1;
			if (0 <= num_n && num_n <= 100001 && visited[num_n] == false) q.push({ num_n , cnt + 1});
			if (num_n == b) {
				End = true;
				break;
			}
		}
	}
}

int main() {
	int a, b; cin >> a >> b;
	if (a < b) {
		bfs(a, b);
		cout << cnt + 1;
	}
	else cout << abs(a - b);
}

chaeaok 4년 전 0

맞은 코드

#include <iostream>
#include <queue>
#include <utility>
#include <cmath>
using namespace std;

bool End = false;
bool visited[200001];
int cnt = 0;

void bfs(int a, int b) {
	queue<pair<int,int>> q;
	q.push({ a, cnt });
	visited[a] = true;
	while (End == false) {
		int num = q.front().first;
		cnt = q.front().second;
		q.pop();
		visited[num] = true;
		for (int i = 0; i < 3; i++) {
			int num_n;
			if (i == 0) num_n = num * 2;
			else if (i == 1) num_n = num - 1;
			else num_n = num + 1;
			if (0<=num_n && num_n <= 200000 && visited[num_n] == false) q.push({ num_n , cnt + 1});
			if (num_n == b) {
				End = true;
				break;
			}
		}
	}
}

int main() {
	int a, b; cin >> a >> b;
	if (a < b) {
		bfs(a, b);
		cout << cnt + 1;
	}
	else cout << abs(a - b);
}

rnjstpgns91 4년 전 0

25번 라인이 잘못됐네요

chaeaok 4년 전 0

어떻게 잘못 되었는지 구체적으로 설명해주실 수 있나요?

djm03178 4년 전 0

배열의 크기가 100001이면 인덱스는 100000까지밖에 없으니 <= 100001이면 안 됩니다.

chaeaok 4년 전 0

아 그렇네요. 감사합니다

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

문제

문제

출처

ICPC

1697번 맞았는데 약간 이해가 안되는 부분이 있어서 질문합니다.

chaeaok 4년 전 2

chaeaok 4년 전 0

rnjstpgns91 4년 전 0

chaeaok 4년 전 0

djm03178 4년 전 0

chaeaok 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말