[백준 15686] 치킨 배달 (python)

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

15686번: 치킨 배달

치킨 배달 문제

전형적인 구현 문제로 요구 조건에 맞게 따라가면서 푸는 문제였다.

조건을 따져가면서 직접 구현하려고 시도했으나, 어디서 코드가 꼬였는지 적은 케이스에선 반복문에서 금방 나가는데 2의 갯수가 7개가 넘어가는 순간 미친듯이 반복문에서 나가지 못해서 해결에 실패했다.

다른사람의 코드를 참고하여 해결 할 수 있었다.

반응형

시도했지만 실패한 코드

# 조건
# 위에서부터 r행, c열 // 단 r과 c는 1부터
# 치킨거리는 집을 기준으로 정해지고 가장 가까운 치킨집과의 거리
# 도시의 치킨 거리는 모든 치킨거리의 합 -> 구해야할 것
# 두 칸 사이의 거리는 |r1-r2|+|c1-c2|
def close(a): # 요구사항인 M개 만큼 치킨집을 폐업해보자
    if a == M:
        global distance_min
        city_copy = copy.deepcopy(city)
        temp = 0
        for i in range(N):
            for j in range(N):
                distance = float('inf')
                if city_copy[i][j] == 1:
                    for rr, cc in chicken(city_copy):
                        if distance > abs(rr-i)+abs(cc-j):
                            distance = abs(rr-i)+abs(cc-j)    
                    temp += distance
        if distance_min > temp:
            distance_min = temp
        return True
    else :
        for r,c in chicken(city):
            city[r][c] = 0
            close(a-1)
            city[r][c] = 2



def chicken(maps): # 치킨 집의 위치를 찾자
    result = []
    for i in range(N):
        for j in range(N):
            if maps[i][j] == 2:
                result.append([i,j])
    return result


import sys
import copy
N, M = map(int, sys.stdin.readline().split())
city = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
distance_min = float('inf')
now_chicken = len(chicken(city))
close(now_chicken) #현재 치킨집 갯수부터 시작
print(distance_min)

먼저 생각한 방법은 치킨집의 위치를 저장해서, 현재 치킨집 개수부터 1개씩 빼가면서 M이랑 맞춰준 후, 해당 케이스에 대해 최소값을 계속 갱신해주는 식으로 풀었는데, 제대로 백트레킹으로 구현하지 않아서 그런가 미친듯이 연산을 했다. 테스트케이스 3개까진 금방나왔는데 너무 아쉬웠다.

정답 코드

# 조건
# 위에서부터 r행, c열 // 단 r과 c는 1부터
# 치킨거리는 집을 기준으로 정해지고 가장 가까운 치킨집과의 거리
# 도시의 치킨 거리는 모든 치킨거리의 합 -> 구해야할 것
# 두 칸 사이의 거리는 |r1-r2|+|c1-c2|
def close(a,b): # 요구사항인 M개 만큼 치킨집을 폐업해보자
    global distance_min
    if a > len(chicken):
        return
    if b == M:
        distance_all = 0
        for r, c in house:
            distance = float('inf')
            for i in val:
                rr, cc = chicken[i]
                distance = min(distance, abs(rr-r)+abs(cc-c))
            distance_all += distance
        distance_min = min(distance_min, distance_all)
        return

    val.append(a)
    close(a+1, b+1)
    val.pop()
    close(a+1,b)

import sys
N, M = map(int, sys.stdin.readline().split())
city = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
chicken, house, val = [], [], []

for i in range(N):
    for j in range(N):
        if city[i][j] == 1:
            house.append([i,j])
        elif city[i][j] == 2:
            chicken.append([i,j])

distance_min = float('inf')
close(0,0)
print(distance_min)

다른사람의 코드를 보고 참고해서 해결한 코드. 큰 틀은 어느정도 비슷하나 백트레킹을 통해 내가 구현한 방식과 다르게 빠르게 해결 할 수 있었다.

---

느낀점

구현 능력이 너무 부족하다 생각해서 구현문제 찾아서 하나씩 시도해보는 중인데 특히 DFS나 백트레킹으로 가면 아직 제대로 해결하지 못할정도로 어려움이 많다. 내가 구현한 코드도 DFS로 시도를 해본건데, 백트레킹 조건을 제대로 못따지고 그래서 계산이 굉장히 많아졌다.

BFS는 어느 수준선에서 해결 할 수 있었다면, DFS는 아직 부족함이 많다는 걸 이 문제를 풀면서 크게 느꼈다. DFS 개념을 다시 정리하고 백트레킹에 대해 제대로 구현하는 법을 이해하면 충분히 풀 수 있는 문제..😥