15686. [Python]치킨 배달

1. 문제

 

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

15686번: 치킨 배달

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 512MB
• 구현
• 브루트 포스

 

3. 파이썬 코드

 

from itertools import combinations


# 들어온 리스트들을 바탕으로 visited 값 갱신해주는 함수
def check_value(first_list, second_list):
    for i in first_list:
        for j in second_list:
            visited[j[0]][j[1]] = min(
                visited[j[0]][j[1]], abs(i[0] - j[0]) + abs(i[1] - j[1])
            )


# 1의 위치, 2의 위치 저장할 리스트
one_pos = []
two_pos = []

N, M = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(N)]
# 행렬 순회하며 1의 좌표와 2의 좌표를 저장
for i in range(N):
    for j in range(N):
        if matrix[i][j] == 1:
            one_pos.append((i, j))
        elif matrix[i][j] == 2:
            two_pos.append((i, j))
# 2의 위치 리스트로 M만큼 조합 생성
two_pos = list(combinations(two_pos, M))
# 최소값 저장 할 변수
ans = 10**6
# 2가 저장된 조합 리스트를 순회하며
for i in two_pos:
    # 거리가 어느정도 되는지 체크할 vistied
    visited = [[10**6] * N for _ in range(N)]
    # 함수에 i 조합과 1의 좌표를 넣어 visited 계산
    check_value(i, one_pos)
    # 임시 변수 생성
    answer = 0
    for i in range(N):
        for j in range(N):
            # 거리값들을 임시변수에 더해줌
            if visited[i][j] != 10**6:
                answer += visited[i][j]
    # 게산이 끝난 임시변수가 최소값보다 작은 경우 값 갱신
    if answer < ans:
        ans = answer

print(ans)

 

4. 문제를 풀고난 후 생각

 

• 최대 M 의 갯수만큼 치킨집을 남겨야 이득을 볼 수 있다고 하기 때문에 어느 치킨집을 남기는 것이 최소값이 되는지 구하는 문제이다.
• 처음에는 단순히 2의 좌표를 처음부터 끝까지 계산 후 최소값을 추출하는 식으로 진행했지만, 최소값이 모두 같은 경우에서 반례가 나와서 이렇게 푸는 방식이 아니라 다른 방식으로 접근해야 하는 것을 생각했다.
• 그렇게 떠올린 방식이 조합을 이용해서 나올 수 있는 모든 경우의 수를 생성한 후 그 모든 경우의 수를 다 탐색을 해가며 최소 치킨 거리가 나오는  값을 출력하는 방식으로 해결했다.

ex)

5 4

1 2 0 2 1

0 0 0 0 0

0 0 2 0 0

0 0 0 0 0

1 2 0 2 1

정답 : 4

이 예시에서 바로 반례가 나왔으며 가운데 2가 없이 나머지 외각의 4개 치킨집을 고르는 방법이 최소 값이 되지만 기존의 작성했던 코드에서는 거리의 최소값이 전부 16으로 같게 나와서 오답처리가 되었다.

 

기존의 코드 ⬇

def check_value(first_list, second_list):
    ans = 0
    for i in first_list:
        for j in second_list:
            visited[j[0]][j[1]] = min(visited[j[0]][j[1]],abs(i[0]-j[0])+abs(i[1]-j[1]))
one_pos = []
two_pos = []

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

matrix = [ list(map(int,input().split())) for _ in range(N) ]
visited = [ [10**6] * N for _ in range(N) ]
for i in range(N):
    for j in range(N):
        if matrix[i][j] == 1:
            one_pos.append((i,j))
        elif matrix[i][j] == 2:
            two_pos.append((i,j))

min_value = 10**6
check = []

for i in two_pos:
    total = 0
    for j in one_pos:
        total += (abs(i[0]-j[0])+abs(i[1]-j[1]))
    check.append(total)
    
if len(check) == M:
    check_value(two_pos,one_pos)
else:
    ans = []
    while M > 0:
        min_check = min(check)
        for i in range(len(check)):
            if check[i] == min_check:
                check.pop(i)
                ans.append(two_pos[i])
                break
        M -= 1    
    check_value(ans,one_pos)
    
answer = 0
for i in range(N):
    for j in range(N):
        if visited[i][j] != 10**6:
            answer += visited[i][j]
print(answer)

 

5. 문제를 푸는데 도움이 되는 지식

 

• 조합
• 구현
• 브루트 포스