[백준] 1697 숨바꼭질(BFS)

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 100001
using namespace std;
bool visit[MAX] = { false, };

void bfs(int start, int finish) {
	queue<pair<int,int>> q;
	int dist = 0; // 경과시간
	pair<int,int> current;

	q.push(make_pair(start,dist));
	visit[start] = true; // 방문여부 check

	while (!q.empty()) {
		current = q.front();
		q.pop();
		if (current.first == finish) break; // 동생 찾을 시 break

		dist = current.second + 1; // 1초씩 증가

		// if문 안의 첫번째 조건은 배열 인덱스 참조 오류를 방지하기 위함(런타임에러 방지)이고,
		// 두번째 조건은 한 번 방문한 노드는 재방문 하지 않게 하기 위함(메모리 초과 방지)
		if (current.first * 2 <= MAX && !visit[current.first * 2]) { // * 2
			q.push(make_pair(current.first * 2, dist)); 
			visit[current.first * 2] = true;
		}
		if (current.first - 1 >= 0 && !visit[current.first - 1]) { // - 1
			q.push(make_pair(current.first - 1, dist));
			visit[current.first - 1] = true;
		}
		if (current.first + 1 <= MAX && !visit[current.first + 1]) { // + 1
			q.push(make_pair(current.first + 1, dist));
			visit[current.first + 1] = true;
		}
		
	}
	
	printf("%d\n", current.second);
}

int main(void) {
	int N, M;
	cin >> N >> M;

	bfs(N, M);
	return 0;
}

 

이번 문제를 통해 코딩은 약간의 허술함도 용납하지 않는다는 것을 다시 깨달았다.

 

처음 메모리 초과는 문제를 한 번만 생각하고 두 번은 생각하지 않아서 발생한 오류. 

visit 배열의 중요성!! -> 한 번 방문한 노드는 다시 방문하게 하지 않게 하기 위함이다.

만약 이 처리를 해주지 않는다면 BFS를 돌릴 때 나처럼 메모리 초과가 뜰 것이다..

 

그리고 런타임 에러는 배열의 인덱스 참조 오류로 인해 발생하였다.

current.first - 1과 같이 마이너스 연산에서는 0보다 작아질 경우를 방지해야 하는데 바보같이 <= MAX 로 해버렸다.

 

BFS를 이용하면 쉽게 풀 수 있는 문제!

 

 

-----------------------------------------------

[추가]

bfs 공부를 하다 더 간단한 코드가 있어서 참고하려고 붙인다.

굳이 큐를 pair로 만들지 않아도 while문을 돌리면서 time을 바로 반환해주면 된다.

 

int bfs(int n, int m) {
    int time = 0;
    queue<int> q;
    q.push(n);
 
    while(1) {
        int size = q.size();
 
        for(int i=0; i<size; i++) {
            n = q.front();
            q.pop();
            if(n == m)
                return time;        
            if(n > 0 && visit[n-1] == 0) {
                q.push(n-1);
                visit[n-1] = 1;
            }
            if(n < 100000 && visit[n+1] == 0) {
                q.push(n+1);
                visit[n+1] = 1;
            }
            if(n*2 <= 100000 && visit[n*2] == 0) {
                q.push(n*2);    
                visit[n*2] = 1;
            }
        }
        time++;
    }
}