백준 1697 : 숨바꼭질 _ C++

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

#그래프 #BFS알고리즘 #silver1

회고

 

✔ 알고리즘 접근 방식

처음엔 문제를 어떤 방식으로 접근하면 좋을지 갈피를 못잡다가 너비 우선 탐색 태그를 보고 힌트를 얻었다.
때문에 dx 배열을 통해 -1, +1, *2 로 이동 방향을 설정 해 주었고 BFS 큐에 이동한 위치와 이동한 횟수를 pair로 함께 저장하여 이동한 위치와 동생의 위치가 일치하게 될 경우 이동한 횟수를 출력해주는 방식으로 구현해줬다.

 

✔ 무수한 런타임 에러..

페이지에 나와있던 단 한개의 테스트 케이스를 통과하는 코드를 작성하는것은 그다지 오래 걸리지 않았다.
그러나 작성한 코드를 채점해보니 런타임 에러가 발생하였고, 해당 원인은 배열의 크기를 초과했기 때문이었다.
런타임 에러가 발생한 것을 확인하고 처음엔 배열의 최대 크기를 조정해줬는데 생각해보니 알고리즘 문제였는데 어이없는 판단이었다.
아무튼, 배열 최대 사이즈를 늘려주어도 런타임 에러가 해결되지 않자 이제서야 예외처리에 문제가 생겼음을 깨닫게 되어 예외처리를 손보기 시작했다.

✔ 예외처리

생각해보니 위치가 50,001 이상일 경우 *2 를 하게 된다면 배열의 범위를 넘어서기 때문에 문제가 발생함을 알게 되었다.

따라서 만약에 *2 를 하였을 때 100,000을 초과하게 된다면 해당 위치는 큐에 넣어주지 않게 처리 해 줬다.

bfs 알고리즘을 수행하기 위해 visit 배열을 통해 앞서 방문했던 위치를 저장하는 방식을 채택했는데, 만약 visit 배열을 먼저 확인하고 위치가 초과했는지 판별한다고 가정했을 때, 위치가 100,000을 초과하게 되었을 경우 해당 인덱스는 존재하지 않기 때문에 런타임 에러가 발생하게 된다.

따라서 위치를 먼저 판별하고, 해당 위치가 초과하지 않는다면 visit 배열을 통해 방문 여부를 체크 해 줬다.
(if 문에서 여러개의 조건식이 존재 할 경우 첫번째 조건식이 성립하지 않는다면 if문을 빠져나가는 특성을 이용하였다.)

if (visit[tmp] != 1 && tmp <= MAX - 1) { //런타임 에러
		visit[tmp] = 1;
		q.push({ tmp,cnt + 1 });
	}

 

if (tmp <= MAX - 1 && visit[tmp] != 1) { //통과
		visit[tmp] = 1;
		q.push({ tmp,cnt + 1 });
	}

해당 문제를 해결하여 런타임 에러가 발생하지 않을거라 생각하고 채점하였으나 또 다시 런타임 에러가 발생하였다.
왜인가 싶어 작성했던 코드를 다시 확인했더니, -1과 +1을 하였을 경우 또한 예외처리를 해줘야 한다는 것을 깨닫게 되어 예외처리를 해줬고 '맞았습니다'가 뜰 수 있었다.

틀렸습니다 는 예외처리를 할 때 부등호 방향을 잘못 써서 틀렸었다 ㅋㅋ

✔ 정리하며

숨바꼭질 문제를 풀며 예외 처리의 중요성을 다시 한번 느낄 수 있었다!!

코드

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

int n, k;
int dx[3] = { -1,1,2 };
int visit[MAX] = { 0, };
queue<pair<int, int>> q;


void move(int x, int cnt) {
	int tmp;
	tmp = x + dx[0]; 
	if (tmp >= 0 && visit[tmp] != 1) {
		visit[tmp] = 1;
		q.push({ tmp,cnt + 1 });
	}

	tmp = x + dx[1];
	if (tmp < MAX - 1 && visit[tmp] != 1) {
		visit[tmp] = 1;
		q.push({ tmp,cnt + 1 });
	}

	tmp = x * dx[2];
	if (tmp <= MAX - 1 && visit[tmp] != 1) {
		visit[tmp] = 1;
		q.push({ tmp,cnt + 1 });
	}

}

int main() {
	cin >> n >> k;
	int tmp;
	int result = 0;
	visit[n] = 1;
	move(n, 0);

	while (!q.empty()) {
		int x = q.front().first;
		int cnt = q.front().second;
		q.pop();
		if (x == k) {
			result = cnt;
			break;
		}
		move(x, cnt);
	}
	cout << result;
	return 0;
}