[BOJ/백준 코딩] 치킨 배달 - PYTHON #15686

소스 코드

# goal은 폐업하지 않을 치킨집의 수
# dfs_temp는 폐업하지 않는 치킨집의 위치 값 저장
def dfs(goal,idx,dfs_temp):
    global res

    # 탈출 조건
    # 폐업하지 않을 치킨집 다 선택했으면
    if len(dfs_temp) == goal:
        length_temp = 0

        # 폐업하지 않을 치킨집의 위치에 따른
        # 치킨 거리들을 goal_temp에 저장하고
        # 이들 중 최소값을 구해서
        # length_temp에 더한다
        for ee in length:
            goal_temp = []
            for eee in dfs_temp:
                goal_temp.append(ee[eee])

            length_temp += min(goal_temp)

        # res보다 length_temp가 작으면
        # swap
        if res > length_temp:
            res = length_temp

        return

    # dfs
    for e in range(idx,len(shop)):
        dfs(goal,e+1,dfs_temp+[e])

    return


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

# 도시
city = [list(map(int,input().split())) for _ in range(n)]

# 집(1)의 위치
house = []

# 치킨집(2)의 위치
shop = []

# 치킨 거리 미리 저장
length = []

# 출력값, 임의의 값
res = 100000

# city를 돌면서 1과 2를 찾아 저장
for q in range(n):
    for w in range(n):
        if city[q][w] == 1:
            house.append([q,w])

        elif city[q][w] == 2:
            shop.append([q,w])

# 치킨 거리를 저장
for qq in house:
    temp = []
    for ww in shop:
        temp.append(abs(qq[0]-ww[0]) + abs(qq[1]-ww[1]))

    length.append(temp)

# 폐업하지 않을 치킨집의 수 == max_num
for max_num in range(1,m+1):
    dfs(max_num,0,[])

print(res)

 

---

해결 방법

1. dfs를 사용한다

 

2. 주어진 m은 폐업하지 않아도 되는 치킨집의 최대 값이다

== m보다 적은 숫자의 치킨집만 남아도 된다

 

3. 집 - 치킨집과의 거리를 미리 계산해두면 반복적인 연산을 조금이라도 피할 수 있다

---

느낀 점

 

ps. 개인적인 코드와 코드를 작성의 이유를 적은 것입니다.

 

오류나 적절치 않은 문법이 존재할 수 있으며, 다른 분들께는 굉장히 비효율적인 방법으로 여겨질 수 있습니다.

 

혹시 개선 사항, 오류 및 문제에 대한 수정 사항 등을 댓글로 남겨주신다면 감사한 마음으로 배우고 수정하겠습니다.