백준 15686 - 치킨 배달

July 11, 2024

🔐 백준 15686 - 치킨 배달

처음 문제를 접근했을 때는, 치킨집의 개수가 최대 13개로 적고, 지도의 크기 또한 $ 50 \times 50 $

이므로 각각의 치킨집을 입력받을 때, 따로 배열에 넣어 치킨집마다 BFS를 활용하여 m개의 치킨집에

대한 거리를 구하려고 하였다.

하지만 굳이 BFS로 거리를 구할 필요가 없었으며, 백트래킹을 통해 m개의 치킨집을 고르고,

고른 치킨집에 대해 치킨 거리를 구해주면 쉽게 풀 수 있는 문제였다. 어떻게 m개의 치킨집을 고를 지에

대한 문제는 두 가지 경우를 생각할 수 있는데, 하나는 DFS와 백트래킹을 활용하여 풀 수 있으며,

또 하나의 방법은 C++의 next_permutation을 이용하여 조합을 구하면 된다.

이 외에도 치킨집을 선택했는지 여부를 확인하는 selected[] 배열을 따로 선언하지 않고, 치킨집에 대한

구조체나 클래스를 선언하여 불필요한 배열 사용을 하지 않는 방식도 고려해볼 수 있다.

struct Chicken {
    int x, y;
    bool selected;
    Chicken(int x, int y) : x(x), y(y), selected(false) {}
};

vector<Chicken> chicken;