[99클럽 5기] 코딩테스트 스터디 15일차 TIL - 백트래킹

[Gold V] 치킨 배달 - 15686 

[문제 링크](https://www.acmicpc.net/problem/15686)

🗝️오늘의 학습 키워드 (Keyword)

• 브루트 포스 (Brute Force)
• 백트래킹

---

💻본인의 언어로 내용 정리 (Today I Learned)

 집과 가장 가까운 치킨 집까지의 거리를 치킨 거리라 한다. 도시에 있는 치킨 집중 M개만을 남겨두고 나머지를 없앴을 때, 도시의 치킨 거리가 최소가 되도록 하는 프로그램을 작성하는 문제이다.

 

💡알고리즘 풀이

N, M = map(int, input().split())

mat = []
for _ in range(N):
    mat.append(list(map(int, input().split())))

homes = [] # 집의 위치 저장
chickens = [] # 치킨 집의 위치 저장
visited = [[0] * N for _ in range(N)] # 방문 표시

ans = [] # 치킨 집 번호와 위치 저장

distance_list = [] # 치킨 거리 저장

# 집의 위치와 치킨 집의 위치 알아내기
for i in range(N):
    for j in range(N):
        if (mat[i][j] == 1):
            homes.append((i, j))
        elif (mat[i][j] == 2):
            chickens.append((i, j))

입력 처리 및 문제를 해결하기 위한 변수와 리스트를 정의한다.

집의 좌표와 치킨 집의 좌표를 각각 리스트에 저장한다.

 

# 치킨 거리 리턴 함수
def chicken_distance():
    total_distance = 0 # 도시 치킨 거리

    for hx, hy in homes:
        distance = 1e9
        
        for id, (cx, cy) in ans:
            distance = min(distance, abs(hx - cx) + abs(hy - cy)) # 최솟값 찾기
        
        total_distance += distance # 도시의 치킨 거리에 더해줌

    distance_list.append(total_distance)

모든 집에 대해서 치킨 거리를 구하면 된다. 함수 처리 과정은 다음과 같다.

1. 먼저 거리를 구하기 위해선 집과 치킨 집의 좌표를 알아야 한다.
2. 집과 치킨 집에 대한 거리의 최솟값인 치킨 거리를 구한다.
3. 모든 치킨 거리를 더하여 도시 치킨 거리를 구한다.

 

# 백트래킹
def chicken(count):
    if (count == M):
        chicken_distance()
        return
    
    for id, (cx, cy) in enumerate(chickens): # 리스트 내 cx, cy와 그에 해당하는 인덱스 번호를 순차적으로 돎돎
        if not (visited[cx][cy]):
            # ans에 저장되어 있다 => 이미 탐색을 진행하였다.
            if ans and (id < ans[-1][0]):
                continue

            visited[cx][cy] = 1
            ans.append((id, (cx, cy)))

            chicken(count+1)

            visited[cx][cy] = 0
            ans.pop()

치킨 집이 최대 M개라는 조건을 적용하기 위해 백트래킹 함수를 정의하였다.

재귀적인 DFS를 이용해 백트래킹을 구현하였다. 조건에 맞지 않는 경우는 가지치기하며 탐색을 진행하도록 한다.

 

🗒️제출 코드

# 15686 치킨 배달

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

mat = []
for _ in range(N):
    mat.append(list(map(int, input().split())))

homes = [] # 집의 위치 저장
chickens = [] # 치킨 집의 위치 저장
visited = [[0] * N for _ in range(N)] # 방문 표시

ans = [] # 치킨 집 번호와 위치 저장

distance_list = [] # 치킨 거리 저장

# 집의 위치와 치킨 집의 위치 알아내기
for i in range(N):
    for j in range(N):
        if (mat[i][j] == 1):
            homes.append((i, j))
        elif (mat[i][j] == 2):
            chickens.append((i, j))

# 치킨 거리 리턴 함수
def chicken_distance():
    total_distance = 0 # 도시 치킨 거리

    for hx, hy in homes:
        distance = 1e9
        
        for id, (cx, cy) in ans:
            distance = min(distance, abs(hx - cx) + abs(hy - cy)) # 최솟값 찾기
        
        total_distance += distance # 도시의 치킨 거리에 더해줌

    distance_list.append(total_distance)

# 백트래킹
def chicken(count):
    if (count == M):
        chicken_distance()
        return
    
    for id, (cx, cy) in enumerate(chickens): # 리스트 내 cx, cy와 그에 해당하는 인덱스 번호를 순차적으로 돎
        if not (visited[cx][cy]):
            # ans에 저장되어 있다 => 이미 탐색을 진행하였다.
            if ans and (id < ans[-1][0]):
                continue

            visited[cx][cy] = 1
            ans.append((id, (cx, cy)))

            chicken(count+1)

            visited[cx][cy] = 0
            ans.pop()

chicken(0)
print(min(distance_list))

---

⬇️전체 소스코드⬇️

hanghae99/python_middler/15일차 치킨 배달/치킨 배달.py at main · Do-heewan/hanghae99