71. 송아지 찾기 [BFS: 상태트리 탐색]

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅

 

 

입력예제 1

5 14

 

출력예제 1

3

 

풀이 

- 1, -1, 5만큼 좌표 이동이 가능하다

=>봉우리 문제 처럼 특정 방향이나 좌표로 이동할 땐 pos변수를 잡고 배열에 이동방향을 명시해서 가면 된다

=>이때 -1이나 10001 같은 유효하지 않은 좌표로 갈 경우에 continue를 사용해서 막아주는 것이 필요하다

- s위치에서 한번에 갈 수 있는 정점을 찾는다 => 5면 6, 4, 10을 탐색

- 해당 위치가 endpoint랑 같으면 ch[x]를 출력한다 => 여기서 ch배열은 단순히 체크의 역할이 아니라 점프 횟수를 누적한다

- ch[pos]가 이닌 이유는 ch[s]=1이기 때문임

 

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
int ch[10001], d[3]={1, -1, 5};

//71. 송아지 찾기 (BFS: 상태트리 탐색)
int main(){
    int s, e, i, x, pos;
    queue<int> Q;
    scanf("%d %d", &s, &e); //현재 위치 S, 송아지 위치 E
    ch[s]=1;
    Q.push(s);
    while(!Q.empty()){
        x=Q.front();
        Q.pop();
        for(i=0; i<3; i++){
            pos=x+d[i]; //가려고 하는 지점
            if(pos<=0 || pos>10000) continue;
            if(pos==e){
                printf("%d\n", ch[x]);
                exit(0);
            }if(ch[pos]==0){
                ch[pos]=ch[x]+1; //점프 횟수
                Q.push(pos);
            }
        }
    }
    return 0;
}