[BOJ] 6716 : Collecting Beepers

문제 링크

6716번: Collecting Beepers (acmicpc.net)

6716번: Collecting Beepers

백트래킹이라고 소개되어있어서 풀어본 문제지만 딱히 백트래킹으로 풀리는 문제가 아니라서 백트래킹 문제로는 추천 안함.

풀이

Karel의 경로를 백트래킹으로 설정해주는 문제인가보다 하고 풀기 시작했다. 하지만 이를 백트래킹으로 구현하기엔 너무 복잡해 보였다.

그래서 계속 생각하다가 그리디 알고리즘을 적용해서 현위치에서 가장 가까운 곳부터 계속해서 이동하면 어떨까 하고 풀어보았더니 예제가 맞았다. 기분좋게 제출했지만 50%에서 틀렸습니다가 나왔다. 이 방법이 틀린 것같아 백트래킹으로 해결하는 방법을 생각해봤지만 떠오르지 않았다. 문제를 푼 사람이 적어 구글링해서 겨우 답을 찾을 수 있었다. 선조의 코드를 참조했는데 next_permutation 을 사용해서 풀었다. next_permutation은 순열 즉 모든 경우를 순서대로 다 해보는 것이다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <climits>
#include <algorithm>
#include <tuple>
#include <cmath>
using namespace std;
typedef long long ll;
const int MAX_N = 40000 + 5;
int N, T;
int st_y, st_x;
int MAX_X, MAX_Y;
vector<pair<int,int>> beeper;
int visited[10];
 
int get_distance() {
    int sum = 0;
    int now_x = st_x, now_y = st_y;
    for (int i = 0; i < beeper.size(); i++) {
        sum += abs(now_x - beeper[i].first) + abs(now_y - beeper[i].second);
        now_x = beeper[i].first;
        now_y = beeper[i].second;
    }
    sum += abs(now_x - st_x) + abs(now_y - st_y);
    return sum;
}
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> T;
    while (T--) {
        cin >> MAX_X >> MAX_Y;
        cin >> st_x >> st_y;
        cin >> N;
        memset(visited, 0, sizeof(visited));
        beeper.clear();
        int x, y;
        for (int i = 0; i < N; i++) {
            cin >> x >> y;
            beeper.push_back({ x,y });
        }
        sort(beeper.begin(), beeper.end());
        int ans = INT_MAX;
        do {
            int temp = get_distance();
            if (temp < ans)
                ans = temp;
 
        } while (next_permutation(beeper.begin(), beeper.end()));
 
        cout << "The shortest path has length ";
        cout << ans << "\n";
    }
    return 0;
}
 
 

결국 모든 경우를 탐색해서 풀 수 있는 쉬운 문제였다. 허무하지만 next_permutation이라는 좋은 스킬을 얻었다.