문제
코드
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100004;
int visited[MAX];
int cnt[MAX];
int main(){
int n, m;
cin >> n >> m;
visited[n] = 1;
cnt[n] = 1;
queue<int> q;
q.push(n);
if(n == m){
cout << '0' << '\n';
cout << '1' << '\n';
return 0;
}
while(q.size()){
int now = q.front();
q.pop();
for(int next : {now-1, now+1, now*2}){
if(0 <= next && next <= MAX){
if(!visited[next]){
q.push(next);
visited[next] = visited[now] + 1;
cnt[next] += cnt[now];
}else if(visited[next] == visited[now] + 1){
cnt[next] += cnt[now];
}
}
}
}
cout << visited[m] - 1 << '\n';
cout << cnt[m] << '\n';
}풀이
가중치가 없는 최단거리 구할 때는 대부분 BFS를 사용한다.
1차원 배열이기 때문에 상,하,좌,우가 아니라 앞,뒤,2배로 이동해야한다.
그 부분을 for(int a : {움직일 위치})로 반복문을 돌며 queue에 집어넣는다.
범위 안에 있는지를 체크하고 queue에 집어넣으며 visited를 하나 올린다.
visited가 최단거리 배열이기 때문에 이는 그냥 하나씩 더하면 되는데
최단 거리로 가는 방법의 수를 구하는 cnt 배열은 좀 다르다.
초기 시작 값을 1로 해두고 갈 길에 이 값을 계속 할당한다.
도착 지점까지 이 길의 cnt 값은 1이 되는 것이다.
가는 길이 겹치는 최단 경로도 있을 수 있기 때문에 else if로 방문했더라도 겹치는 길이라면 cnt에 1을 더해준다.
여기까지 하면 일반적인 출력 값은 다 구할 수 있다.
하지만 입력 값에서 n 과 m의 값이 같은 경우의 예외를 처리해줘야 한다.
그 부분을 if문으로 설정한다.
결과
후기
BFS임을 생각해내지 못한게 좀 아쉽다.
그리디적인 부분으로 하나씩 구현하려다 보니 변수가 너무 많아가지고 힘들었다.
BFS 구현에서도 기본적인 BFS의 흐름을 제외한 주어진 조건들을 생각해서 구현하는게 조금은 어려웠다
:)