카테고리 없음

[백준 15686] 치킨 배달

🥭맹2 2021. 4. 19. 01:05

1. 문제

www.acmicpc.net/problem/15686

 

15686번: 치킨 배달

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

www.acmicpc.net

2. 접근 방법

총 치킨 가게에서 M개만 골라야하니 -> 조합으로 풀면 되겠다고 생각했습니다.

 

조합을 배열에 담고, 해당 치킨 가게들 중 집과 가장 가까운 거리에 있는 치킨 거리를 총합에 더해주고,

 

결과 값인 minAns를 갱신해주면 된다고 생각했습니다.

 

그리고 NxN에서 N의 최대값이 50이고, M의 최대값이 13이라 각각의 조합에서 완탐을 해도 될거같은 느낌을 받았습니다.

흠 ~! 완탐이라는 표현이 맞는지 ^-^~!

 

여튼 조합을 itertools로 구현하지 않고 직접 구현해서 풀었슴다. (아마 라이브러리 사용이 안될 것이라고 생각하므로)

3. 코드

python

def solve(cnt, total):
    global minAns, chicken_group, homes
    if cnt == len(homes):
        minAns = min(minAns, total)
        return
    temp_dist = 1e9
    for i in range(M):
        temp_dist = min(temp_dist, abs(homes[cnt][0]-chicken_group[i][0]) + abs(homes[cnt][1]-chicken_group[i][1]))
    total += temp_dist
    solve(cnt+1, total)


def comb(cnt, start):
    global M
    if cnt == M:
        solve(0, 0)
        return

    for i in range(start, len(chickens)):
        chicken_group.append(chickens[i])
        comb(cnt+1, i+1)
        chicken_group.pop()

N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
homes = []
chickens = []
minAns = 1e9

for y in range(N):
    for x in range(N):
        if board[y][x] == 1:
            homes.append((x, y))
        elif board[y][x] == 2:
            chickens.append((x, y))

chicken_group = []
comb(0, 0)
print(minAns)

4. 마치며

예전에는 조합 만드는 것두 쩔쩔매던 나였지만 ! 이제 조합도 직접 구현할 수 있다 이겁니다 !