Written by JS970
on February 28, 2023

1697 - 숨바꼭질

난이도: 실버 1
날짜: 2023년 2월 28일
상태: Correct/Retry
추가 검토 여부: Yes
알고리즘 : BFS, DFS, DP, Graph

solution

K가 N보다 작을 경우 N은 K로 이동하기 위해 한 칸씩 뒤로 가는 경우밖에 없다. 따라서 K가 N보다 작거나 같은 경우에 대해서는 예외 처리를 한다.
이제 나머지 경우인 K가 N보다 큰 경우에 대해서만 생각한다.
N이 K까지 도달하기 위해서는 한 칸 앞으로 가거나 뒤로 가는 연산을 적절히 한 후 가능한 경우 2배 연산까지 활용해야 한다.
아래는 내가 생각한 아이디어이다.
- arr배열은 index, distance를 pair형태로 저장하는 배열이다.
- arr배열의 index는 0부터 K까지의 값을 가지며, distance는 기본적으로 K-index의 값으로 초기화된다.(한 칸씩 움직여서 도달하는데 걸리는 시간)
- calc라는 함수를 통해 arr배열에서 2배 연산을 통해 이동 가능한 지점에 대한 배열 값을 초기화한다.
  - arr[k] = 0 → arr[k/2] = 1 → arr[k/2/2] = 2 …
  - k가 짝수인 경우라면 위 연산만으로 초기화하면 되지만 k가 홀수인 경우라면 k/2, (k/2)+1 에 대해서 모두 초기화 해 준다. 이 경우에는 1칸 움직인 후 2배 연산을 하기 떄문에 짝수인 경우와 달리 2초의 시간을 더해 준다.
  - 수가 작은 경우(1, 3, 5 등) 짝수와 홀수인 경우에 대해 곱셈 연산을 해서 이동하는 것보다 1칸씩 이동하여 연산하는 것이 더 빠를 수 있다. 이러한 경우를 포함시키기 위해 원래 배열의 값과 연산값 중 작은 값을 선택하도록 코드를 작성한다.
  - arr[k/2]등에 대한 연산이 종료되었다면 calc를 재귀 호출하여 해당 수에서의 곱셈 이동에 대해 배열을 계속해서 초기화한다.
  - k==1일 경우 함수를 종료한다.
위의 아이디어를 떠올리는 데까지 시행착오가 몇 번 있었지만 정상적으로 작동함을 확인했따.
그런데… 이 문제를 위와 같이 풀면 DP를 사용해서 풀이한 것이 된다. 하지만 백준에서 이 문제의 카테고리는 그래프 이론, 그래프 탐색, BFS이다. 그래프 이론을 이용하여 다시 풀어보자
DP는 DAG에 대해서만 사용해야 한다고 한다. 본 문제처럼 정점의 방문 선후 과계가 명확하지 않은 경우에는 사이클에 의해 잘못된 답을 구할 수 있게 된다고 한다…
- DAG : Directed Acyclic Graph, 유향 비순환 그래프
- DAG에서는 한번 거친 노드로 다시 돌아오지 않는다.
- 본 문제에서 나의 알고리즘은 한번 거친 노드로 다시 돌아오는 부분이 있다.
- 하지만 출발 노드 자체가 다르고 이러한 중복되는 노드에 대해 최솟값 연산을 통해 처리했다.

code

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

void calc(pair<int, int> arr[], int k)
{
    if(k == 1) return;
    if(k%2 == 0)
    {
        arr[k/2].second = (arr[k/2].second < arr[k].second + 1) ? arr[k/2].second : arr[k].second + 1;
        calc(arr, k/2);
    }
    else
    {
        arr[k/2].second = (arr[k/2].second < arr[k].second + 2) ? arr[k/2].second : arr[k].second + 2;
        arr[(k/2)+1].second = (arr[(k/2)+1].second < arr[k].second + 2) ? arr[(k/2)+1].second : arr[k].second + 2;
        calc(arr, k/2);
        calc(arr, (k/2)+1);
    }
}

int main()
{
    int N, K;
    cin >> N >> K;
    if(K <= N) cout << N - K << endl; 
    else
    {
        pair<int, int> * arr = new pair<int, int>[K+1];
        for(int i = 0; i <= K; i++) arr[i] = {i, K-i};
        calc(arr, K);

        vector<pair<int, int>> point;
        for(int i = 0; i < K; i ++)
           point.push_back(arr[i]);
        
        int min = 999999;
        for(auto p : point)
            min = (min < p.second + abs(p.first - N)) ? min : p.second + abs(p.first - N);
        cout << min << endl;      
    }
    return 0;
}

ref

1697번: 숨바꼭질

글 읽기 - 반례, 지적 부탁드릴게요ㅠㅠ

유향 비순환 그래프

Top