[BOJ/백준] 15686번 치킨 배달 (Python 파이썬)

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	512 MB	56263	27285	16173	45.061%

 

문제

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다.

이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.

임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.

예를 들어, 아래와 같은 지도를 갖는 도시를 살펴보자.

0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 1 2

0은 빈 칸, 1은 집, 2는 치킨집이다.

(2, 1)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |2-1| + |1-2| = 2, (5, 5)에 있는 치킨집과의 거리는 |2-5| + |1-5| = 7이다. 따라서, (2, 1)에 있는 집의 치킨 거리는 2이다.

(5, 4)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |5-1| + |4-2| = 6, (5, 5)에 있는 치킨집과의 거리는 |5-5| + |4-5| = 1이다. 따라서, (5, 4)에 있는 집의 치킨 거리는 1이다.

이 도시에 있는 치킨집은 모두 같은 프랜차이즈이다. 프렌차이즈 본사에서는 수익을 증가시키기 위해 일부 치킨집을 폐업시키려고 한다. 오랜 연구 끝에 이 도시에서 가장 수익을 많이 낼 수 있는  치킨집의 개수는 최대 M개라는 사실을 알아내었다.

도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.

둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다.

도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.

 

출력

첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.

 

예제 입력 1 

5 3
0 0 1 0 0
0 0 2 0 1
0 1 2 0 0
0 0 1 0 0
0 0 0 0 2

예제 출력 1 

5

예제 입력 2 

5 2
0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
2 0 0 1 1
2 2 0 1 2

예제 출력 2 

10

예제 입력 3 

5 1
1 2 0 0 0
1 2 0 0 0
1 2 0 0 0
1 2 0 0 0
1 2 0 0 0

예제 출력 3 

11

예제 입력 4 

5 1
1 2 0 2 1
1 2 0 2 1
1 2 0 2 1
1 2 0 2 1
1 2 0 2 1

예제 출력 4 

32

 

---

풀이

문제에 이것 저것 조건이 되게 많이 있네요. 우선은 문제를 조금 단순하게 만들어 보겠습니다.
조건 중에서 치킨 집의 개수를  M개로 제한하고 있습니다. 이 조건을 제거해보고 문제를 바라보면 단순해 집니다.
모든 집에 대해서 치킨 거리를 구하면 됩니다. 해당 과정은 다음과 같이 정리됩니다.

1. 각 집(좌표 1)마다 모든 치킨 집에 대해서 거리를 계산한다.
2. 그 중 최솟값을 해당 집의 "치킨 거리"로 정한다.
3. 1번, 2번을 반복하며 모든 집에 대해서 치킨 거리를 구한다.
4. 모든 치킨 거리를 더하여 해당 도시의 치킨 거리를 구한다.

위 과정을 함수 getDistance로 만들면 다음과 같이 작성할 수 있습니다.

def getDistance():
    x = 0
    # 집을 기준으로 치킨 거리를 계산. 한 집에 대해 여러 개의 치킨집 거리 계산
    for hx, hy in homes:
        distance = 1e9
        for cx, cy in chicken:
            distance = min(distance, abs(hx-cx)+abs(hy-cy))
        x += distance # x는 모든 집에 대한 치킨 거리
    distance_list.append(x)

 

이제 다시 M개라는 제한 조건을 적용해 보겠습니다. 
어떻게 구현할까요? 우선, brute force 기법으로 모든 경우의 수에 대해서 값을 구한 뒤, 비교를 통해 최솟값을 구할 수 있겠네요. 하지만 여기서 백 트래킹 기법을 사용하면 효울적으로 해결할 수 있습니다.

문제를 보고서 제한 조건을 설정한 후, 조건에 맞지 않는 경우는 가지치기를 통해 검토하지 않으며 진행해야 합니다.

https://great-park.tistory.com/38?category=1293104 

[BOJ/백준] 2529번 부등호 (Python 파이썬)

이전에 풀이했던 부등호 문제와 다른 문제들과 같이 항상 같은 패턴으로 진행하시면 됩니다.

def solve(depth):
    if depth == M:
        getDistance()# 치킨집을 하나씩 추가하면서 M개가 되었을 때 추가
        return

    for id, (cx, cy) in enumerate(chickens):
        if not visited[cx][cy]: #방문 안 한 치킨집에 대하여
            if ans and id < ans[-1][0]:# 이전 solve에서 검토한 치킨 집은 건너뛰어도 됨
                continue
            visited[cx][cy] = 1
            ans.append((id, (cx, cy)))
            solve(depth+1)
            visited[cx][cy] = 0
            ans.pop()

백 트래킹의 의미를 생각해 보면, 제한 조건을 적용하여 검토하는 node의 수를 확연히 줄이는 것입니다.
더불어서 재귀적인 DFS를 통해서 Backtrack을 구현하는 것입니다.

제약 조건 만족 문제 (Constraint Satisfaction Problem) 에서 해를 찾기 위한 전략해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack (다시는 이 후보군을 체크하지 않을 것을 표기)하고, 바로 다른 후보군으로 넘어가며, 결국 최적의 해를 찾는 방법

 

결국 이와 같은 문제 유형은, 주어진 제한 조건을 DFS에 잘 녹여내어 탐색을 실시하고, 약간의 구현을 통해 정답을 구하면 됩니다.

 

최종 코드

from sys import stdin
input = stdin.readline
N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]

# 1은 집, 2는 치킨집
homes = []
chickens = []
# 추가한 치킨집
ans = []
# 방문 목록
visited = [[0]*N for _ in range(N)]
# 거리 목록
distance_list = []

for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            homes.append((i, j))
        elif graph[i][j] == 2:
            chickens.append((i, j))


def getDistance():
    x = 0
    # 집을 기준으로 치킨 거리를 계산. 한 집에 대해 여러 개의 치킨집 거리 계산
    for hx, hy in homes:
        distance = 1e9
        for id, (cx, cy) in ans:
            distance = min(distance, abs(hx-cx)+abs(hy-cy))
        x += distance # x는 모든 집에 대한 치킨 거리
    distance_list.append(x) 


def solve(depth):
    if depth == M:
        getDistance()# 치킨집을 하나씩 추가하면서 M개가 되었을 때 추가
        return

    for id, (cx, cy) in enumerate(chickens):
        if not visited[cx][cy]: #방문 안 한 치킨집에 대하여
            if ans and id < ans[-1][0]:# 이전 solve에서 검토한 치킨 집은 건너뛰어도 됨
                continue
            visited[cx][cy] = 1
            ans.append((id, (cx, cy)))
            solve(depth+1)
            visited[cx][cy] = 0
            ans.pop()


solve(0)
print(min(distance_list))