728x90
반응형
목차
https://www.acmicpc.net/problem/12851
문제
코드 구현
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
int visit[100001] = { 0 }; //시간 카운트
int N, K;
int cnt[100001] = { 0 }; //방법 수 카운트
int methods = 0;
int sec = 0;
vector<int> track;
void bfs() {
queue<int> q;
q.push(N);
visit[N] = 1;
cnt[N] = 1;
while (!q.empty()) {
int t = q.front();
q.pop();
if (t == K)
{
return;
}
for (int next : {t * 2, t - 1, t + 1}) {
//범위 초과나는지 여부 확인
if (next < 0 || next > 100000)
continue;
if (!visit[next]) {
q.push(next);
visit[next] += visit[t] + 1;
//경우의 수는 각각의 수를 더한 것이다.
cnt[next] += cnt[t];
}
// 시각이 같을 경우를 고려해주어야 한다
else if (visit[next] == visit[t] + 1)
cnt[next] += cnt[t];
}
}
}
int main() {
cin >> N >> K;
bfs();
cout << visit[K]-1 << "\n";
cout << cnt[K];
}
/*
5 100000
*/
반응형
'백준 문제풀이' 카테고리의 다른 글
[백준][bfs] 14497 주난의 난 c++ 구현 (0) | 2024.06.27 |
---|---|
[백준][bfs] 13913 숨바꼭질4 c++ 구현 (2) | 2024.06.26 |
[백준][재귀함수] 1780 종이의 개수 c++ 구현 (0) | 2024.06.21 |
[백준][bfs] 12869 뮤탈리스크 c++구현 (0) | 2024.06.20 |
[백준][bfs] 4179 불! c++ 구현 (0) | 2024.05.12 |