백준 1697번 C++ 풀이

https://www.acmicpc.net/problem/1697

시간 제한	메모리 제한	solved.ac 티어
2초	128MB	실버 1

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

---

이 문제는 푼지 꽤 됐는데, 어째서인지 글이 안써져 있었다. 그래서 간단하게 작성한다.

 

이 문제는 처음보면 그래프탐색인걸 몰랐다. 이 문제를 풀때는 최단거리라는 알고리즘 개념은 없었지만, 어째서인지 bfs를 돌리다가 맨 처음 K를 찾으면, 그게 답일 것 같았다. 머리속에서도 그래프를 그려보니 맞는 것 같아 bfs를 돌려봤다. 왜 bfs로 찾은 거리가 최단거리냐면, 간선의 가중치가 모두 같기 때문이다.(이건 이 문제를 풀고 한참 있다가 알게 되었다.)

 

#include <bits/stdc++.h>
#define MAX 100001
using namespace std;

void solution(int start, int target, int time) {
    int ans;
    bool visited[MAX] = {false, };
    queue<pair<int, int>> q; // pair -> (location, time)
    q.push(make_pair(start, 0));
    visited[start] = true;

    while(!q.empty()) {
        int loc = q.front().first;
        int t = q.front().second;
        q.pop();

        if (loc == target) {
            ans = t;
            break;
        }

        if (loc + 1 < MAX && !visited[loc + 1]) {
            q.push(make_pair(loc + 1, t + 1));
            visited[loc + 1] = true;
        }
        if (loc * 2 < MAX && !visited[loc * 2]) {
            q.push(make_pair(loc * 2, t + 1));
            visited[loc * 2] = true;
        }
        if (loc - 1 >= 0 && !visited[loc - 1]) {
            q.push(make_pair(loc - 1, t + 1));
            visited[loc - 1] = true;
        }
    }
    cout << ans;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int start, target;
    cin >> start >> target;
    solution(start, target, 0);
}

 

 

문제풀면 바로바로 쓰자...