[C++] 백준(BOJ) - 12851 : 숨바꼭질 2

27 Oct 2023 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 알고리즘
• 풀이
• 코드
• 평가

문제

백준(BOJ) - 12851 : 숨바꼭질 2(링크)

알고리즘

1. 그래프이론
2. BFS

풀이

1. 최단 거리 찾기 문제 - BFS
2. 경우의 수 찾기 - Cnt 배열을 이용
   • 경우의 수는 가능한 방법의 총합으로 이루어진다
3. 반례

코드

// BOJ-12851 : 숨바꼭질 2
#include<bits/stdc++.h>
using namespace std;

const int MAX = 200002;
int n, k;
int visited[MAX+4];
long long cnt[MAX+4];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> k;

	if (n == k)
	{
		puts("0"); puts("1");
		return 0;
	}

	queue<int> q;

	q.push(n);
	visited[n] = 1;
	cnt[n] = 1;

	while (q.size())
	{
		int now = q.front();
		q.pop();

		for (int next : {now - 1, now + 1, now * 2}) // 3방향 탐색
		{
			if (next < 0 || next > MAX) continue;
			if (!visited[next])
			{
				q.push(next);
				visited[next] = visited[now] + 1;
				cnt[next] += cnt[now]; // 방문한 적이 없을 때는 cnt 추가
			}
			else if(visited[next] == visited[now] + 1) // 최단거리 일때만 cnt를 추가 하기(최단거리가 아닌 경우는 카운팅하면 안된다)
			{
				cnt[next] += cnt[now];
			}
		}
	}
	cout << visited[k] - 1 << '\n';
	cout << cnt[k] << '\n';
		
	return 0;
}

평가

• 일차원 좌표에서 BFS를 구현할 수 있다
• cnt 배열을 이용해 경우의 수를 체크할 수있다
• 테스트케이스의 반례를 생각하기
  • 문제에서 주어진 예시가 다른 경우 => 같은 경우일 때도 생각해보기
  • 문제 범위의 최대, 최소값을 대입해서 시뮬레이션 해보기