[백준 / C언어] 1697번: 숨바꼭질 (BFS 풀이)

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

1697번: 숨바꼭질

 

난이도: solved.ac 실버 1

 

 

알고리즘 분류

---

그래프 탐색 (BFS)

 

구현 방법

---

수빈이의 위치와 이동 횟수(찾는 시간)를 저장할 구조체 LOC를 만들어주었다.

BFS에서 사용할 큐는 LOC형 배열로 만들어주었고 index는 100001까지로 해주었다.

내 풀이에서 주목해야 할 점이 있는데 -1 만큼 이동할 때 loc가 0보다 작아지면 안 되는 것이고,

+1 만큼 이동할 때는 loc가 K보다 작아야 하며, X2 만큼 순간 이동할 때는 loc가 K + 1보다 작거나 같아야 한다는 것이다.

-1 만큼 이동하거나 +1 만큼 이동할 때의 제약 조건은 설명 안해도 알 테고, X2 만큼 순간이동할 때 loc가 K + 1보다 작거나 같아야 하는 것의 이유는,

사실 K + 1보다 커져도 되긴 하지만, 배열의 크기 제약도 문제가 되기도 하고, X2 한 위치가 K + 2보다 커버리면 최적의 루트에서 벗어나기 때문에 K + 1보다 작거나 같게 한 것이다.

 

코드

---

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define MAX 100001

typedef struct _LOC {
	int loc;
	int order;
} LOC;

LOC q[MAX];
int visited[MAX];

int main() {
	int N, K;
	scanf("%d %d", &N, &K);

	int front = 0, rear = 0;
	q[rear].loc = N;
	q[rear].order = 0;
	visited[N] = 1;

	while (q[front].loc != K) {
		int newloc;
		if (q[front].loc > 0) {
			newloc = q[front].loc - 1;
			if (!visited[newloc]) {
				rear++;
				q[rear].loc = newloc;
				q[rear].order = q[front].order + 1;
				visited[newloc] = 1;
			}
		}
		if (q[front].loc < K) {
			newloc = q[front].loc + 1;
			if (!visited[newloc]) {
				rear++;
				q[rear].loc = newloc;
				q[rear].order = q[front].order + 1;
				visited[newloc] = 1;
			}
		}
		if (q[front].loc * 2 <= K + 1) {
			newloc = q[front].loc * 2;
			if (!visited[newloc]) {
				rear++;
				q[rear].loc = newloc;
				q[rear].order = q[front].order + 1;
				visited[newloc] = 1;
			}
		}
		front++;
	}
	printf("%d", q[front].order);
	return 0;
}