문제

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

맨하탄 거리 개념

문제 개념

초반에 BFS를 사용해서 풀려고 생각을 했는데 |r1-r2| + |c1-c2| 로 구하는 경우 big O(1)의 성능을 보여주므로 BFS가 더 느릴수도 있다.

0은 빈 칸, 1은 집, 2는 치킨집이다.

풀이

예제1 house, chicken 위치확인

from itertools import combinations

N, M = map(int, input().split())
# 좌표의 쌍들을 리스트로 넣어줌
house = []
chicken = []

for i in range(N):
    # enumerate: 한줄 통째로 입력받음, index & value를 한번에 가져올수 있음
    for j, v in enumerate(map(int, input().split())):
        print(f'({i}, {j}): {v}', end='')

    print()

예제1 house, chicken append

from itertools import combinations

N, M = map(int, input().split())
# 좌표의 쌍들을 리스트로 넣어줌
house = []
chicken = []

for i in range(N):
    # enumerate: 한줄 통째로 입력받음, index & value를 한번에 가져올수 있음
    for j, v in enumerate(map(int, input().split())):
        if v == 1:
            house.append((i, j))
        if v == 2:
            chicken.append((i, j))
print(f'houses: {house}')
print(f'chickens: {chicken}')

enumerate의 value가 1일 경우 house로 append
enumerate의 value가 2일 경우 chicken으로 append

전체코드

임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|

def get_dist(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

도시의 치킨 거리의 최솟값

ans = 2 * N * len(houses)

도시의 치킨 거리 구하기

for combi in combinations(chickens, M):
    # 도시 치킨의 거리
    total = 0
    for house in houses:
        total = total + min(get_dist(house, chicken) for chicken in combi)
    print(f'combi: {combi}, total: {total}')
    ans = min(ans, total)

print(ans)

전체코드

from itertools import combinations

N, M = map(int, input().split())
# 좌표의 쌍들을 리스트로 넣어줌
houses = []
chickens = []

for i in range(N):
    # enumerate: 한줄 통째로 입력받음, index & value를 한번에 가져올수 있음
    for j, v in enumerate(map(int, input().split())):
        if v == 1:
            houses.append((i, j))
        if v == 2:
            chickens.append((i, j))


# 임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|
def get_dist(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])


# 도시의 치킨 거리의 최솟값
ans = 2 * N * len(houses)

for combi in combinations(chickens, M):
    # 도시 치킨의 거리
    total = 0
    for house in houses:
        total = total + min(get_dist(house, chicken) for chicken in combi)
    print(f'combi: {combi}, total: {total}')
    ans = min(ans, total)

print(ans)

입력예제1

입력예제2

입력예제3

입력예제4