백준 1697 숨바꼭질 C++

요즘 DFS, BFS 문제를 풀고 있는데, 한 번 감이 잡히니까 문제가 계속 잘 풀려서 감사한 마음이 든다.

 

BFS 문제를 풀 때는 Queue를 사용해서 문제를 풀 수 있는데, 내가 초반에 많이 실수 했던 부분은 노드의 방문 기록을 남기는 작업을 하지 않았었다.

 

이제는 습관을 잡아, 무조건 DFS든 BFS든 visited 배열을 항상 만들고 시작한다.

 

아래 문제는 전형적인 BFS 문제인데, 이 문제에서 핵심은 수빈이가 동생을 찾기 위한 방법이 3가지라는 것이다.

 

방법 1. 현재 위치 - 1

방법 2. 현재 위치 + 1

방법 3. 현재 위치 x 2

 

나 같은 경우는 보통 DFS, BFS 문제를 풀 때, 구조체를 활용해서 움직이는 객체를 생성한다.

 

queue를 생성하고, 초기 위치를 push 해준다.

이 후 while문을 돌면서 현재 위치가 동생의 위치와 일치할 때까지 반복하여 돌면 된다.

 

이 문제는 위치 정보만 있으면 되서 1차원 배열로도 충분히 문제를 풀 수 있다.

 

수빈이의 현재 위치 정보를 변경해주는 것은 for 문으로 와서 수빈이가 다음에 옮겨갈 위치 정보를 방법 1, 2, 3을 적용해 현재 위치를 변경해준 값을 다시 queue에 push 해주면 된다.

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <queue>

using namespace std;

struct INFO {
	int loc, time = 0;
};

const int MAX_SIZE = 100000;
int N, K, min_time;

int LOCATION[MAX_SIZE] = { 0, };
int visited[MAX_SIZE] = { 0, };

void bfs() {
	// Start Finding
	int time = 0;

	queue<INFO> q;
	INFO start;
	start.loc = N;
	start.time = 0;;

	q.push(start);

	while (!q.empty()) {
		if (q.front().loc == K) {
			min_time = q.front().time;
			break;
		}

		INFO cur = q.front();
		q.pop();

		// Method of Location Transition
		for (int m = 0; m < 3; ++m) {
			int next_loca;
			if (m == 0) {
				next_loca = cur.loc - 1;
			}
			else if (m == 1) {
				next_loca = cur.loc + 1;
			}
			else {
				next_loca = cur.loc * 2;
			}
			
			if (visited[next_loca] == 0 && next_loca >= 0 && next_loca <= MAX_SIZE) {
				INFO temp;
				temp.loc = next_loca;
				temp.time = cur.time + 1;
				
				visited[next_loca] = 1;
				q.push(temp);
			}
		}
	}
}

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

	bfs();

	printf("%d", min_time);

	return 0;
}