[백준] 15686 - 치킨 배달 [Python(파이썬)]

'삼성 SW 역량 테스트' 기출 문제 입니다. 😀
문제 👉 15686번: 치킨 배달

1. 문제

1. N*N 도시의 각 칸은 빈 칸(0), 집(1), 치킨집(2) 중 하나이다.
2. 치킨 거리는 집이 (r1, c1)이고, 치킨집이(r2, c2)일 때, |r1-r2| + |c1-c2| 이다.
3. 최대 M개의 치킨집을 고르고, 도시의 치킨 거리의 최솟값을 출력한다.

2. 풀이

브루트포스를 이용한 문제 풀이

1. 집과 치킨집 위치를 저장한다.
2. 브루트포스를 통해 모든 경우의 유효한 치킨집 조합을 통해 치킨거리의 최솟값을 구한다.

3. 코드

N, M= map(int, input().split())
B = [list(map(int, input().split())) for _ in range(N)]
home, chicken, v = [], [], []
ret = float('inf')

def solution():

    def dfs(idx, cnt):
        global ret
        if idx > len(chicken):
            return
        if cnt == M:
            val = 0
            for hx, hy in home:
                d = float('inf')
                for i in v: # 집과 가장 가까운 치킨집과의 치킨 거리 구하기
                    cx, cy = chicken[i]
                    d = min(d, abs(hx - cx) + abs(hy - cy))
                val += d # 각 집의 치킨 거리 더하기
            ret = min(ret, val) 
            return

        # v는 유효한 치킨집의 인덱스
        v.append(idx) # 현재 치킨집 포함 O
        dfs(idx+1, cnt+1) 
        v.pop() #현재 치킨집 포함 X
        dfs(idx+1, cnt) 

    # 1. 집과 치킨집 위치 찾기
    for i in range(N):
        for j in range(N):
            if B[i][j] == 1:
                home.append((i+1,j+1))
            elif B[i][j] == 2:
                chicken.append((i+1,j+1))

    dfs(0, 0)
    return ret

print(solution())

• 결과 : 500 ms

---

References

•  

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋