백준 1697 - 숨바꼭질

문제링크

• 백준 1697

오답을 이끌었던 문제 접근

• 수빈이의 현재 위치를 X, 동생의 위치를 K라고 했을 때, 동생이 수빈이보다 왼쪽에 위치하는 경우 X=X-1, 동생이 수빈이보다 오른쪽에 위치하는 경우 X=X+1 또는 X=2*X 로 이동할 수 있을 것이라 생각했다.
• 따라서 BFS를 구현할 때도 방문표시배열이 필요가 없었으며 수빈이의 위치와 동생의 위치가 같아지는 경우를 탈출 조건으로 선택하였다.
• 방문한 노드에는 현재 위치 정보와 시간을 담을 수 있도록 구조체를 활용하였다.

잘못된 접근이었던 이유

• 동생이 수빈이보다 왼쪽에 있건, 오른쪽에 있건 수빈이가 움직일 수 있는 방향에 대한 제약은 없다. (올바른 문제 접근 시 수빈이가 방문한 좌표로 다시 방문하지 않도록 제한을 두는 것과는 별개로)
• 수빈이가 현재 위치(X)에서 -1만큼 이동한 후 순간이동(x2)을 하는 경우도 고려할 수 있어야 한다.

문제 접근 방향 (Solution)

• 수빈이가 이동할 수 있는 모든 경우의 수에 대해서 너비우선탐색을 진행한다.
• 수빈이가 방문한 좌표는 다시 방문하지 않는다.
• 좌표 정보, 시간 정보를 함께 담을 수 있도록 구조체를 선언한다.

구현 결과

#include <iostream>
#include <queue>
#include <memory.h>
using namespace std;

typedef struct _ele
{
	int pos;
	int time;
} Ele;

bool visited[100001]; // 방문표시

bool check_valid(int pos)
{
	if (0 <= pos && pos <= 100000 && visited[pos]==false)
		return true;
	else
		return false;
}

int bfs(int x, int k)
{
	memset(visited, false, sizeof(visited));

	Ele el = { x, 0 }; // 처음 위치와 시간 정보
	int next_pos1, next_pos2, next_pos3, time;
	queue<Ele> q;
	q.push(el);

	while (!q.empty())
	{
		el = q.front();
		time = el.time;
		visited[el.pos] = true;
		q.pop();

		if (el.pos == k)
			return el.time;

		next_pos1 = el.pos - 1;
		next_pos2 = el.pos + 1;
		next_pos3 = el.pos * 2;

		if (check_valid(next_pos1))
		{
			el.pos = next_pos1;
			el.time = time + 1;
			q.push(el);
		}
		if (check_valid(next_pos2))
		{
			el.pos = next_pos2;
			el.time = time + 1;
			q.push(el);
		}
		if (check_valid(next_pos3))
		{
			el.pos = next_pos3;
			el.time = time + 1;
			q.push(el);
		}
	}
}


int main()
{
	int n, k; // 수빈이의 처음 위치(n), 동생의 위치(k)
	cin >> n >> k;

	int ans = bfs(n, k);

	cout << ans << endl;
	return 0;
}