[Python] 백준 15686번 치킨 배달 풀이

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

15686번: 치킨 배달

백트랙킹을 사용하는 문제입니다.

import sys
sys.setrecursionlimit(10**8)
sys.stdin = open('111.txt')

N,M = map(int,input().split()) # N은 격자 사이즈, M은 치킨집 개수
graph = []
house = []
chicken = []


for col in range(N):
    graph.append(list(map(int,input().split())))
    for row in range(N):
        if graph[col][row] == 1:
            house.append((col,row))
            
        elif graph[col][row] == 2:
            chicken.append((col,row))

기본적으로 먼저 짜둬야 하는 코드들입니다.

그래프 정보를 받을 때, 집과 치킨집의 좌표를 따로 받아줍니다.

 

이제 백트랙킹을 이용해서 각 집마다 치킨집과의 거리를 다 구해볼게요.

2차원에서 각 좌표들끼리의 조합을 구하는 방법은 거의 공식처럼 쓰입니다.

혹시, 이 문제를 풀기 전에 백준에서 N과M 시리즈를 푸셨다면 1차원에서 조합을 짜는 법은

손에 익으셨을텐데요. 2차원에선 막막할겁니다.

 

안그렇다구요? 재능러시군요.

 

저는 일단 이 문제를 처음 봤을 때, combinations을 쓰면 풀 수는 있지만 재귀를 사용해서 풀고자 했습니다. 근데 아이디어가 안 떠올라서 모 블로그를 참고해서 구현하는 방법을 참고했어요. 알고보니 공식처럼 쓰이더라구요.

 

2차원에서 좌표를 조합하는 방법부터 먼저 짚고 가겠습니다. 금방합니다!

arr = []
def back(num,cnt):
    if num>len(chicken):
        return
    
    if cnt==M:
        for idx in arr:
            cx,cy = chicken[idx]
            print((cx,cy),end=" ")
        return

    arr.append(num)
    back(num+1,cnt+1)
    arr.pop()
    back(num+1,cnt)

(back(0,0))

자, 이게 공식처럼 쓰이는 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

구분이 잘 안가있지만

(0,1) , (3,0)

(0,1) , (4,0)

(0,1) , (4,1)

.

.

.

이런 식으로 좌표가 스윽 나옵니다.

여기서 num > len(chicken)의 역할은 치킨 리스트에 담은 좌표들의 개수보다 넘어가면 인덱스에러가 뜨기때문에, 그걸 잡아주는 역할을 합니다. cnt는 최대 몇개의 좌표를 뽑을지 보는 것이라 cnt==M이 되면 이제 좌표 쌍을 뽑도록 합니다.

 

위 코드는 그냥 공식처럼 받아들이시면 됩니다.

 

그렇게 치킨 좌표들 다 뽑았으면 이제 집이랑 같이 이중 포문 돌려서 각각의 거리들을의 모든 합을 다 구해주면 됩니다.

그걸 min함수를 이용해서 계속 갱신해주면 되겠습니다.

 

아래는 해답코드이며 복붙해가실 때는 sys.stdin = open 이부분 주석처리해주세요~

import sys
sys.setrecursionlimit(10**8)
sys.stdin = open('111.txt')

N,M = map(int,input().split()) # N은 격자 사이즈, M은 치킨집 개수
graph = []
house = []
chicken = []


for col in range(N):
    graph.append(list(map(int,input().split())))
    for row in range(N):
        if graph[col][row] == 1:
            house.append((col,row))
            
        elif graph[col][row] == 2:
            chicken.append((col,row))


arr = []
real_check = int(1e9)
def back(num,cnt):
    global real_check
    if num>len(chicken):
        return
    
    if cnt==M:
        result_tot = 0
        for hx,hy in house:
            min_check = int(1e9)
            for idx in arr:
                cx,cy = chicken[idx]
                min_check = min(min_check,abs(hx-cx)+abs(hy-cy))
                
            result_tot+=min_check
            
        real_check = min(result_tot,real_check)
        return

    arr.append(num)
    back(num+1,cnt+1)
    arr.pop()
    back(num+1,cnt)
    return real_check

print(back(0,0))