71. 송아지 찾기(BFS : 상태트리탐색)

it 취업을 위한 알고리즘 문제 풀이

문제

코드1

//71. 송아지 찾기(BFS : 상태트리탐색)
#include <stdio.h>
#include <algorithm>
int main() {
    //freopen("input.txt", "rt", stdin);
    int s, e, delta = 0, cnt = 0;
    scanf("%d %d", &s, &e);

    if (s < e) {
        while (1) {
            if (abs(e - s) <= 3) {
                delta = abs(e - s);
                cnt += delta;
                break;
            }
            else {
                s += 5;
                ++cnt;
            }

            if (s == e)
                break;

        }
    }
    else if (s > e) {
        cnt = s - e;
    }

    printf("%d", cnt);
    return 0;
}

코드2

//71. 송아지 찾기(BFS : 상태트리탐색)
#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
int main() {
    freopen("input.txt", "rt", stdin);
    int s, e, x, nx;
    scanf("%d %d", &s, &e);


    int checkCnt[10001] = {0,};
    int dirx[] = { -1,1,5 };
    queue<int> Q;

    Q.push(s);
    checkCnt[s] = 1;

    while (!Q.empty()) {
        x = Q.front();
        Q.pop();
        for (int dir = 0; dir < 3; ++dir) {
            nx = x + dirx[dir];

            if (nx <= 0 || nx > 10000)
                continue;
            if (nx == e) {
                printf("%d", checkCnt[x]);
                exit(0);
            }
            if(checkCnt[nx] == 0){    
                Q.push(nx);
                checkCnt[nx] = checkCnt[x] + 1;
            }
        }

    }

    return 0;
}

문제해결방법

• 첫 번째 풀이
  • 이동 방법이 +5, +1, -1밖에 없기 때문에 최소로 방문을 계산하기 위해서는 송아지가 나보다 오른쪽에 있는 경우와 왼쪽에 있는경우를 나누어서 생각해야 한다.
  • 송아지가 나보다 왼쪽에 있다면 +5칸을 사용할일 없이 나와 송아지 차이만큼 왼쪽으로 가기만 하면 최소값이 나온다.
  • 반대로 송아지가 나보다 오른쪽에 있다면 송아지와 나와의 거리차이를 계산해주어 +5칸을 갈지 아닐지 생각해주어야 한다. 그 차이가 3이하라면 +5칸 이동없이 차이만큼 이동하면 된다.
  • 만약 송아지와 나와의 거리 차이가 4,5,6라면 +5를 이동하고 그 차이만큼 추가로 -1 or +1칸 해주면 된다.
  • 이렇게 송아지와 나와의 차이를 이동할 때마다 체크 해주어 같게 되면 break 하고 같지 않다면 거리차이를 비교하여 3이하일때는 현재 카운트에 차이만큼 더해주고 3초과일때를 +5칸 이동하고 카운트값을 증가시켜주고 위 과정을 반복한다.
• 두 번째 풀이
  • 최소 거리, 최소 간선 수, 최소 ... 횟수 등 최소의 무엇을 구할 때 나랑 인접한 곳을 먼저 탐색하는 BFS자주 사용된다. 각 노드로 이동시 가중치가 없다면 당연히 나와 연결되어 있는 곳을 통해 가는 것이 최소이동방법이 될 수밖에 없다. 이 문제에서는 이동 횟수의 최소를 구하는 문제이기 때문에 BFS를 통해 구할 수 있다. 이동횟수는 한번 이동할 때마다 모두 1씩 카운트 하는 이동횟수를 모두 1로 하는 비가중치로 볼 수 있다. 
  • 이 문제에서는 이동방법이 +5, +1, -1로 갈 수 있는 좌표가 현재 위치에서 인접한 곳이 된다.이렇게 인접한 곳을 차례로 큐에 넣으면서 넓이 우선 탐색을 진행하면 된다.
  • 이때 시간복잡도를 줄이기 위해 현재 위치로 부터 구한 인접한 곳이 이미 방문했던 곳이거나 문제의 주어진 조건을 벗어나는 좌표라면 더이상 이 노드로부터는 탐색을 진행하지 않도록 큐에 넣지 않고 다른 인접한 곳을 찾는다. 그리고 인접한 곳이 문제의 주어진 조건에 부합하는 곳이라면 해당곳에서 원하는 연산을 수행하면 되는데, 여기서는 이동 횟수를 출력하면 된다.
  • 이동횟수를 구하는 방법은 인접한 곳을 탐색해 큐에 넣을 때마다 직전 노드 +1을 하여 해당 노드로 가는 점프 횟수를 누적하면 된다.
  • 이 코드에서는 초기 위치를 방문처리를 위해 1부터 시작했기 때문에 마지막에 end위치에서 점프이동횟수를 출력할 때 현재노드를 가리키는 인덱스에 출력회수가 아니라 직전노드까지의 점프 횟수 데이터를 출력하면 된다.