[BOJ] 1697 - 숨바꼭질 (C++)

1. 알고리즘

이 문제는 BFS 알고리즘으로 풀 수 있는 문제이다. 즉, Queue를 사용하여 문제를 푼다.

2. 전체 소스

#include <iostream> #include <queue> using namespace std; //1697 const int MAX = 200000; int check[MAX+1]; // 탐색 시 해당 값을 이미 방문했는지의 여부를 확인하기위해 사용되는 배열 int dist[MAX+1]; // 트리의 깊이를 구하기 위하여 사용되는 배열 (몇번만에 찾는지 확인하기위함) int main() { int subin, sis; cin >> subin >> sis; queue <int> q; q.push(subin); // 초기 값을 Queue에 넣어준다. check[subin] = 1; // 초기 값은 무조건 방문 여부를 true로 설정하여 시작하여야 한다. dist[subin] = 0; // 초기 값의 깊이는 0이다. while (!q.empty()) { int now = q.front(); q.pop(); if (now == sis) // 동생의 위치를 찾으면 loop문을 빠져나온다. break; if (now-1 >= 0 && !check[now-1]) { // -1 했을 때 값을 방문했는지 여부를 확인 q.push(now - 1); check[now - 1] = 1; dist[now - 1] = dist[now] + 1; // 현재 위치한 깊이에서 +1을 해준다. } if (now + 1 > 0 && now + 1 < MAX && !check[now + 1]) { // +1 했을 때 값을 방문했는지 여부 확인 q.push(now + 1); check[now + 1] = 1; dist[now + 1] = dist[now] + 1; } if (now * 2 > 0 && now * 2 < MAX && !check[now * 2]) { // *2 했을 때 값을 방문했는지 여부 확인 q.push(now * 2); check[now * 2] = 1; dist[now * 2] = dist[now] + 1; } } cout << dist[sis] << endl; return 0; }

3. 참고 사항

처음에 런타임 오류가 발생했다. 
백준에서 런타임 오류가 발생하는 경우는 대게 배열의 메모리 할당 공간 문제의 이유로 발생하게 된다. 즉 사용하고자 하는 메모리 공간보다 할당되어 있는 메모리 공간이 작을 경우 발생하게 된다. 나의 경우는 now변수로 check와 dist 배열의 크기가 동적으로 할당되는데, 이때 해당 변수가 MAX값 보다 작을때의 조건을 추가해주어서 런타임 오류를 해결했다.

if (now * 2 > 0 && now * 2 < MAX && !check[now * 2]) {

4. 문제

백준 알고리즘 : https://www.acmicpc.net/problem/1697