치킨 배달

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

삼성 알고리즘 시험 보러 가서 못 푼 문제이다.

1. 다시 푸는데 오랜 걸렸다. ( 2018.08.01 ) : 조합 + BFS
2. 다시 푸는데 30분도 안걸렸다. ( 2018.10.01 ) : DFS

첫 번째 풀이

1. 치킨집 K개 중에 M개를 고르는 경우의 수를 구한다. (조합)
2. 선택되지 않은 치킨집은 빈 칸으로 만든다.
3. 각 집을 출발점으로 가장 가까운 치킨집까지의 거리를 구한다 (BFS)

첫 번째 풀이 예시

• 다음과 같이 치킨집이 3개가 있다고 하자.
  • 0번 치킨집
  • 1번 치킨집
  • 2번 치킨집
• 최대 2개의 치킨집을 선택하는 경우의 수는 다음과 같다.
  • 0번, 1번 — A
  • 0번, 2번 — B
  • 1번, 2번 — C
• A를 생각해보자.
  • 2번이 선택되지 않았기 때문에, 2번 치킨집을 폐업 시킨다.
  • 각 집의 위치에서 BFS를 실행한다. 이는 각 집에서 가장 가까운 치킨 집과의 거리를 구하기 위함이다.
• B, C도 위와 같은 작업을 반복한다.

두 번째 풀이

1. 치킨을 선택하여 List에 저장한다. (DFS)
2. 각 집에서 선택된 치킨집 까지의 거리를 계산한다.

치킨집이 A, B, C, D 네 개 있고, 최대 3개 선택을 한다고 했을 때, DFS는 다음과 같이 진행된다.