인덱스를 통한 배열 접근 시 항상 조심하자

백준 1697번을 풀다 발견한 논리 오류다.

종종 발생할 수 있는 문제라 여겨 기록을 해둔다.

 

처음에는 이렇게 코드를 작성했다. 논리적으로는 알고리즘이 문제가 없어보이는데 계속 런타임 오류가 났다.

#include <iostream>
#include <queue>
#define MAX 100000
using namespace std;

int S, D;
int dx[3] = { 1,-1,2 };
bool visited[MAX] = { 0, };
queue<int> q;

void bfs() {
	int x=S, nx, level=0;
	q.push(x);
	visited[x]= true;

	while (!q.empty()) {
		int q_size = q.size();
		while (q_size--) {
			x = q.front();
			q.pop();

			if (x == D) {
				cout << level << "\n";
				return;
			}

			for (int i = 0; i < 3; i++) {
				if (i == 2) 
					nx = x * 2;
				else 
					nx = x + dx[i];

				if (!visited[nx] && nx >= 0 && nx <= MAX) {
					visited[nx] = true;
					q.push(nx);
				}
			}
		}
		level++;
	}
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);

	cin >> S >> D;

	bfs();
	return 0;
}

 

처음에는 도저히 이유를 모르겠어서 MAX 값도 바꿔봤는데 계속 런타임 에러가 뜨길래 질문 검색 코너를 찾아봤다.

이 문제를 보면 런타임 에러 뜨는 코드를 제출한 경우가 무척 많다.

 

질문 코너의 도움을 받아 드디어 통과한 코드다.

#include <iostream>
#include <queue>
#define MAX 100001
using namespace std;

int S, D;
int dx[3] = { 1,-1,2 };
bool visited[MAX] = { 0, };
queue<int> q;

void bfs() {
	int x=S, nx, level=0;
	q.push(x);
	visited[x]= true;

	while (!q.empty()) {
		int q_size = q.size();
		while (q_size--) {
			x = q.front();
			q.pop();

			if (x == D) {
				cout << level << "\n";
				return;
			}

			for (int i = 0; i < 3; i++) {
				if (i == 2) 
					nx = x * 2;
				else 
					nx = x + dx[i];
			
				if (nx < 0 || nx >= MAX) continue;
				if (!visited[nx]) {
					visited[nx] = true;
					q.push(nx);
				}
			}
		}
		level++;
	}
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);

	cin >> S >> D;

	bfs();
	return 0;
}

 

딱 한 부분만 바꿨다. 이 부분을

if (!visited[nx] && nx >= 0 && nx <= MAX) {}

아래처럼 바꿨다.

if (nx < 0 || nx >= MAX) continue;
if (!visited[nx]) {}

nx가 범위를 초과해버리면 미리 반복문 내의 다음으로 점프하게 만들었다.

이렇게 하지 않으면 visited[nx]가 true인지 false인지 검사할 때 존재하지 않는 인덱스 -1을 조회하게 된다.

배열에 존재하지 않는 인덱스를 찾아보려 하니 당연히 에러가 뜬다.