[Inflearn] 송아지 찾기(BFS : 상태트리탐색)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

     - 직선상의 좌표

     - 앞으로 1, 뒤로 1, 앞으로 5 이동 가능

     - 최소 몇 번의 점프로 송아지의 위치까지 갈 수 있는가

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

현수의 위치(S), 송아지의 위치(E) 가

5 14 라고 주어졌을 때,

5부터 14까지 가야하는데,

1, 5, -1 이라는 숫자를 최소로 사용하여 14 를 만들 때 (중복 사용 가능)

갈 수 있는 최소 횟수를 구하는 문제로 바꾸어 풀 수 있다.

5에서 14까지 도달하기 위해서

5+1+1+1+1+1+1+1+1+1

5+5+1+1+1+1

5+5+5-1

...

모든 경우의 수를 확인하여 최소 횟수를 구하면 된다.

먼저 pos = 5 일 때를

1번 정점이라고 생각하면

5에서 +1, +5 -1 을 하는 3가지의 경우가 있다.

즉 하나의 정점에 세 개의 다리가 생긴다(?)고 생각하면 된다.

그림으로 그려보면 외계인 같..다

내가 그려서 외계인 같은 걸수도..

시작하기 전 먼저 5를 Queue 에 넣어준다.

그리고 14에 도달했을 때, 이동의 최소횟수 즉 트리의 level 을 구하기 위해

node 번호도 저장해야할 것 같다.

Queue 에서 원소를 뺄 때 node++ 해주면 된다.(초기 노드는 0으로 초기화)

(14에 도달하였을 때 반복문을 종료하고, 그 때의 node 번호를 이용해서 level 을 구하면 된다.)

node 번호를 구하면서 하려고 했는데 너무 복잡해진다ㅠㅠ

중복연산을 줄이기 위해 방문하지 않는 노드들이 생기기 때문이다..

방문하지 않는 노드들 가지 신경쓰다보니 복잡하다 복잡해..

결국 level 을 구하는 힌트를 얻었다.

엄청 단순했다.. 하핳 이걸.. 결국 힌트까지 얻다니..

check 배열에 방문여부를 저장하면서 지금 레벨도 알 수 있도록 저장하는 것이다.

일단 해보자.

Queue

5

시작! Queue 에서 5를 빼고, 

5에서 할수 있는 이동 +1, +5, -1 의 결과를 Queue 에 push 한다.

또, 결과를 ch 배열에 넣어주면서 이미 한 연산을 중복해서 하지 않도록 해준다.

(위 그림에서 X 표 쳐진 5, 11, 5, 9 는 중복되는 연산이다.)

Queue

6  10  4

move[] = {1, 5, -1};    // 이동할 수 있는 거리

while(!q.empty())

{

x = q.front();

q.pop();

flag = false;

for(i=0;i<3;i++)

pos = x + move[i];

if(pos == E)

endFlag = true;

break;

if(ch[pos] == 0])

q.push(pos);

ch[pos] = ch[x] + 1;

if(endFlag)

rst = ch[x] + 1;

break;

}

 

마찬가지로 6을 queue 에서 빼고

이동한 후 거리를 Queue 에 push 해준다.

여기서 5는 이미 체크상태이므로 queue 에 넣지 않고 pass

Queue

10  4 7 11 5

다음 10 을 queue 에서 빼고

이동한 거리를 Queue 에 push

마찬가지로 11은 이미 체크상태이므로 queue 에 넣지 않고 pass

Queue

4 7 11 11 15 9

...

Queue

15 9 3 ...

15에서 이동할 때 

Queue

9 3 ... 16 20 14

14가 나오게 된다.

그러면 if(pos == e) 조건에 걸리게 되고, for 문에서 나온 후,

rst 에 거리를 저장하고 while 문도 종료된다.

BFS 도 DFS 처럼 재귀함수를 쓰진 않지만

재귀함수만큼의 매력이 있는 것 같다.

BFS 도 얼릉 익숙해져야지!

#. Code

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int ch[10001], mv[3] = { 1, 5, -1 };
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    int s, e, i, x, pos, rst = 0;
    bool endFlag;
    queue<int> q;
 
    scanf("%d %d", &s, &e);
 
    q.push(s);
 
    while (!q.empty())
    {
        x = q.front();
        q.pop();
        endFlag = false;
 
        for (i = 0; i < 3; i++)
        {
            pos = x + mv[i];
 
            if (pos == e)
            {
                endFlag = true;
 
                break;
            }
 
            if (ch[pos] == 0)
            {
                q.push(pos);
                ch[pos] = ch[x] + 1;
            }
        }
 
        if (endFlag)
        {
            rst = ch[x] + 1;
 
            break;
        }
    }
 
    printf("%d\n", rst);
 
    return 0;
}

#. Other code

#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
 
int ch[10001], d[3]={1, -1, 5};
 
int main(){
    int s, e, x, pos, i;
    queue<int> Q;
 
    scanf("%d %d", &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;
}

강사님은 flag 를 사용하지 않으시고 송아지가 있는 좌표에 도달하면 결과를 출력하고 exit(0) 를 동작시켜

프로그램이 종료되도록 하셨다.

그리고 내가 놓쳤던 부분이 있는데,

line 25에서 좌표는 1부터 10,000 까지이므로 좌표를 벗어나면 작업을 해줄 필요가 없다.

그러므로 0과 10,000 을 벗어나는 구간은 continue 처리를 해서 최적화시켜줄 수 있었다.

#. Result

  - Input --------------------------------------------------------

5 14

------------------------------------------------------------------

  - Output --------------------------------------------------------

3

------------------------------------------------------------------