[BOJ] [Python] 15686번 : 치킨 배달

문제를 정리해보자.

 

 

• 도시 : N x N
  • 빈칸 : 0
  • 집 : 1
  • 치킨집 : 2
• 도시의 칸 : (r, c) (각각 1부터 시작한다.)

 

• 치킨 거리 : 집과 가장 가까운 치킨집 사이의 거리
• 도시의 치킨 거리 : 모든 집의 치킨 거리의 합

 

• 거리 계산 : | r1 - r2 | + | c1 - c2|

 

가장 수익을 많이 낼 수 있는 치킨집의 개수, 최대 M개를 이용하여

도시의 치킨 거리의 최솟값을 출력하면 되는 문제이다.

 

 

먼저, 최대 M개를 선택해야 하는 점에 주목하자.

치킨집은 M개를 제외하고는 모두 폐업시킬 것이다.

 

완전탐색으로 생각하자면, 치킨집이 M개되는 모든 경우의 수를 따져주면 된다.

 

 

n, m = map(int, input().split())

chicken = []
house = []

dp = [[0] * (n + 1) for _ in range(n + 1)]

m_chicken = []

max_result = []

for i in range(1, n + 1):

    j = 1
    for num in map(int, input().split()):

        if num == 1:
            house.append([i, j])

        elif num == 2:
            chicken.append([i, j])

        j += 1


def cal():
    global max_result

    result = []

    for h in house:

        distance = 1e9
        for c in m_chicken:
            tmp = abs(h[0] - c[0][0]) + abs(h[1] - c[0][1])

            if tmp < distance:
                distance = tmp

        result.append(distance)

    max_result.append(sum(result))


def select_chicken(cnt):
    if cnt == m:
        cal()
        return

    for idx, val in enumerate(chicken):

        i = val[0]
        j = val[1]

        if dp[i][j] == 0:
            if m_chicken:
                if idx < m_chicken[-1][1]:
                    continue

            dp[i][j] = 1

            m_chicken.append((val, idx))

            select_chicken(cnt + 1)

            dp[i][j] = 0
            m_chicken.pop()


select_chicken(0)
print(min(max_result))

 

 

select_chicken 함수는 치킨집 M개를 선택하는 재귀함수이다.

M개를 선택할 때, 주의할 점은 조합으로 하면 안 된다.

 

예를 들어,

1, 2, 3, 4, 5 가 있다. 여기서 3개를 뽑아야 한다고 하자.

 

이때, 1 2 3을 뽑았다면 1 3 2는 순서만 바뀐 순열이므로 뽑으면 안 되는 것이다.

(왜냐하면 치킨집의 '위치'를 따지는 것이기 때문에 필요 없다.)

 

조합으로 뽑지 않고, 순열로 뽑기 위해서

현재 뽑아야 하는 치킨집은, 마지막으로 뽑은 치킨집보다 index가 작으면 안 되도록 하였다.

 

정상적으로 치킨집이 M개가 뽑혔다면, cal 함수가 실행된다.

 

치킨집은 방금 뽑힌 M개만 있다고 가정하자.

그리고 집마다 각각의 치킨 거리를 구해준다.

모든 치킨 거리의 합을 구하면, 이는 도시의 치킨 거리가 된다.

 

이렇게 치킨 집 M개의 모든 경우의 수마다, 도시의 치킨 거리를 구해주고

이중 가장 작은 값이 도시의 치킨 거리 최솟값이 된다.

 

 

 

 

이전에 풀었던 연구소 문제와 비슷했다.

[BOJ] [Python] 14502번 : 연구소 다시 작성하자