[C언어] 백준 1697 숨바꼭질

반응형

문제

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

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

입력

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

출력

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

예제 입력 1 

5 17

예제 출력 1 

4

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

1697번: 숨바꼭질

 

문제 풀기 전 로직 생각하기

---

얼핏보면 DP 문제로도 보일 수 있지만 이 문제는 BFS 문제입니다.

저희가 아는 일반적인 BFS 문제는 2차원 배열에서 진행되지만 이 문제는 1차원 배열 문제입니다.

 

저희가 2차원 BFS 문제를 풀 때는 보통 상하좌우를 큐에 삽입하면서 이동합니다.

1차원 배열은 좌우로 밖에 못움직이죠

그러면 그냥 좌우만 큐에 삽입하면서 이동하면 되기에 어렵게 생각할 필요 없을 것 같습니다.

현재 위치에서 -1, +1, * 2 를 삽입하면서 이동시키고 상대와 맞닿았을 때 종료시키면 될 것 같습니다.

 

전체 코드

---

#include <stdio.h>

int	n, m, pos = -1, last = 0, cur = 0, map[100001] = {};
int	q[200002];

int main()
{
	scanf("%d %d", &n, &m);
	if (n == m)
    {
        printf("0\n");
        return (0);
    }
	q[last++] = n;
    // 큐가 비기전 이면서 상대와 맞닿지 않았을 때까지 
	while (cur < last && map[m] == 0)
	{
		pos = q[cur++];
        // 이전 위치에 가본적이 없다면
		if (0 <= pos - 1 && map[pos - 1] == 0)
		{
			q[last++] = pos - 1;
			map[pos - 1] = map[pos] + 1;
		}
        // + 1 위치에 가본적이 없다면
		if (pos + 1 <= 100000 && map[pos + 1] == 0)
		{
			q[last++] = pos + 1;
			map[pos + 1] = map[pos] + 1;
		}
        // * 2 위치에 가본적이 없다면
		if (pos * 2 <= 100000 && map[pos * 2] == 0)
		{
			q[last++] = pos * 2;
			map[pos * 2] = map[pos] + 1;
		}
	}
	printf("%d\n", map[m]);
	return (0);
}

 

문제 해설

---

문제 풀기 전 로직 생각하기 부분에서 말했던걸 기준으로 작성 했습니다.

BFS의 while 조건문을 큐를 비울때 까지 면서 상대와 맞닿기 전일때 까지로 주고

-1, +1, *2 모두 한 번도 밟지 않은 땅일 때만 움직이면서 카운트를 해주었습니다.

while이 끝난 후 상대 위치값을 출력 해주는 방식으로 풀어 보았습니다.

 

 

2차원 배열이 아닌 1차원 배열이라서 좌우로만 움직이면 되기에 좀 더 쉽게 풀 수 있었습니다.

이해가 잘 되지 않으시다면 유튜브 바킹독님의 BFS 강의 마지막 문제를 참고하시면 좋을것 같습니다!