[백준 알고리즘] 12851번 - 숨바꼭질 2 (BFS에서의 같은 depth 처리과정)

1. 문제 및 예시 실행결과

 

 BFS문제인 것은 파악했는데 visited 배열을 처리하는 과정에서 조금 힘들었다. 논리적으로 길을 먼저 세워 풀면 되는 문제를 너무 급하게 덥벼든 것 같다. visited를 배열에 삽입하기 전에 처리하는 것이 좋을 수 있지만(Queue가 커지는 것을 방지) 이 문제 처럼 같은 depth의 중복을 처리해야하는 문제는 queue에서 노드를 꺼내서 visited처리를 하는게 좋을 수 있다는 것을 깨달았다. 다음은 예외 케이스이다.

---

1 3

---

 

출처: https://www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

---

---

2. 풀이 과정

 

 문제 쪼개기

 

1. 최단거리를 구하지 못한 상황에서는 변수에 값 저장 후 case값 1증가

2. 최단거리를 구한 상황에서

 - node의 count가 ans_count 보다 크다면 continue

 - node의 count가 ans_count와 같고 위치가 K와 같으면 case값 1증가

 

다음은 코드다

 

#include <iostream>
#include <queue>

using namespace std;

bool visited[100001] = { 0 };

int main(void) {
	int N, K;
	queue<pair<int, int>> q;

	int		ans_count	= NULL;
	int		ans_case	= 0;
	bool	ans_dir		= false;

	cin >> N >> K;

	visited[N] = true;
	q.push(make_pair(0, N));

	while (!q.empty()) {

		int count = q.front().first;
		int current = q.front().second;
		q.pop();

		visited[current] = true;

		if (ans_dir && count > ans_count)
			continue;
		
		if (current == K && !ans_dir) {
			ans_dir = true;
			ans_case++;
			ans_count = count;
			continue;
		}

		if (ans_dir && current == K && ans_count == count) {
			ans_case++;
			continue;
		}

		if(current + 1 < 100001 && !visited[current + 1]){
			q.push(make_pair(count + 1, current + 1));
		}

		if (current - 1 >= 0 && !visited[current - 1]) {
			q.push(make_pair(count + 1, current - 1));
		}

		if (current * 2 < 100001 && !visited[current * 2]) {
			q.push(make_pair(count + 1, current * 2));
		}
	}

	cout << ans_count << endl << ans_case;

	return 0;

}

 

이전 코드는 visited를 넣어줄때 처리했다. 어휴... 하루를 날렸다... 이 문제의 교훈은 "탐색을 진행할 때 같은 depth의 노드는 통과한다면 visited는 node를 queue에서 꺼내고 처리하다." 이다.