N x N 2차원 배열로 이루어진 도시가 있고, 각 칸은 빈칸, 집, 치킨집 중 하나라고 합니다. 그리고 (a, b)와 (c, d) 사이의 거리는 | c - a | + | d - b | 로 구하고, 여러 개의 치킨 집중에 M개를 골라 각 집과 치킨집 거리 최솟값의 합을 구하라는 문제입니다.
문제에서 맨 위 맨 왼쪽의 좌표는 (1, 1)인 것 같지만, 우리는 배열에 저장해서 했으므로 맨 위 맨 왼쪽의 좌표는 (0, 0)으로 두고 문제를 풀 것 입니다. 이래도 치킨집과 집 사이의 거리를 구하는 공식은 그대로 사용할 수 있기 때문에 문제가 없습니다.
여러 개의 치킨 집중에서 M개를 고르라는 것은 순열과 조합을 이용하라는 것이고, 치킨집을 뽑는 순서와 상관없기 때문에 조합을 사용하겠습니다.
이 문제는 총 3번으로 나눠서 풀도록 하겠습니다.
입력값 받기
치킨집과 집 좌표 저장하기
조합을 사용해서 최솟값 구하기
입력값 받기
n과 m을 입력받고, 2차원 배열을 입력하는 것은 쉽게 할 수 있을 겁니다. 그리고 우리는 조합을 사용하니까 itertools.combinations를 불러옵니다.
from itertools import combinations as cbn, m =map(int,input().split())arr =list(list(map(int,input().split())) for _ inrange(n))
우리는 최솟값을 출력해야 하므로 ans 변수를 만들고 거기에 큰 값을 저장합니다. ans의 초깃값은 대각선으로 끝과 끝의 거리인 100 * 13 = 1300을 해도 상관없고, 그 이상의 값이나 파이썬은 float('inf')로 무한대로 설정해주면 됩니다.
from itertools import combinations as cbn, m =map(int,input().split())arr =list(list(map(int,input().split())) for _ inrange(n))ans =float('inf')
치킨집, 일반 집 좌표 저장하기
치킨 집 좌표를 저장할 곳은 Chicken, 일반 집 좌표를 저장할 곳은 Home이라고 합시다.
이제 for문을 사용하여 arr을 하나하나 확인하면서 Chicken, Home에 좌표를 저장하면 됩니다.
from itertools import combinations as cbn, m =map(int,input().split())arr =list(list(map(int,input().split())) for _ inrange(n))ans =float('inf')Chicken = []Home = []for i inrange(n):for j inrange(n):if arr[i][j] ==2: Chicken.append((i,j))if arr[i][j] ==1: Home.append((i,j))
C++ 같은 경우에는 pair<int, int>로 저장해서 vector에 넣는 것이 더 편할 것 같습니다.
조합을 사용해서 최솟값 구하기
조합을 이용해서 치킨 집중에서 m개를 골라야 합니다. 그래서 choice에 조합을 저장해주면 됩니다.
from itertools import combinations as cbn, m =map(int,input().split())arr =list(list(map(int,input().split()) for _ inrange(n)))ans =float('inf')Chicken = []Home = []for i inrange(n):for j inrange(n):if arr[i][j] ==2: Chicken.append((i,j))if arr[i][j] ==1: Home.append((i,j))choice =cb(Chicken, m)
이제 for문을 돌리는데 range를 사용하지 않고 돌리는 것이 가독성이 훨 좋습니다.
from itertools import combinations as cbn, m =map(int,input().split())arr =list(list(map(int,input().split())) for _ inrange(n))ans =float('inf')Chicken = []Home = []for i inrange(n):for j inrange(n):if arr[i][j] ==2: Chicken.append((i,j))if arr[i][j] ==1: Home.append((i,j))choice =cb(Chicken, m)for choice_chicken in choice: blah blah
choice_chicken은 치킨집을 m개 선택하였으니 이제 선택한 치킨집의 좌표와 모든 일반 집의 좌표를 확인하면서 집마다 가장 가까운 치킨집의 거리를 구해야 합니다.
from itertools import combinations as cbn, m =map(int,input().split())arr =list(list(map(int,input().split())) for _ inrange(n))ans =float('inf')Chicken = []Home = []for i inrange(n):for j inrange(n):if arr[i][j] ==2: Chicken.append((i,j))if arr[i][j] ==1: Home.append((i,j))choice =cb(Chicken, m)for choice_chicken in choice:for hx, hy in Home:for cx, cy in choice_chicken: blah blah
각 집에서 m개의 치킨집의 거리의 합을 비교하며 가장 가까운 거리의 치킨집을 찾아야 하기 때문에 dist라는 변수를 만들어주고, 각 집에서 가까운 치킨집의 거리를 구한 dist 값을 한 곳에 더해서 모든 값의 최소 거리를 구해야 하므로 res라는 변수를 만들어주어야 합니다. 그리고 마지막으로 res 변수는 ans에 비교하여 ans의 값을 더 작은 값으로 업데이트하면 됩니다.
거리를 구하는 공식은 | a - c | + | b - d | 이므로 dist = min(dist, abs(a-c)+abs(b-d))를 해주면 됩니다.
from itertools import combinations as cbn, m =map(int,input().split())arr =list(list(map(int,input().split())) for _ inrange(n))ans =float('inf')Chicken = []Home = []for i inrange(n):for j inrange(n):if arr[i][j] ==2: Chicken.append((i,j))if arr[i][j] ==1: Home.append((i,j))choice =cb(Chicken, m)for choice_chicken in choice: res =0for hx, hy in Home: dist =float('inf')for cx, cy in choice_chicken: dist =min(dist, abs(hx - cx) +abs(hy - cy)) res += dist ans =min(ans, res)
그리고 이제 출력을 해주면 됩니다.
from itertools import combinations as cbn, m =map(int,input().split())arr =list(list(map(int,input().split())) for _ inrange(n))ans =float('inf')Chicken = []Home = []for i inrange(n):for j inrange(n):if arr[i][j] ==2: Chicken.append((i,j))if arr[i][j] ==1: Home.append((i,j))choice =cb(Chicken, m)for choice_chicken in choice: res =0for hx, hy in Home: dist =float('inf')for cx, cy in choice_chicken: dist =min(dist, abs(hx - cx) +abs(hy - cy)) res += dist ans =min(ans, res)print(ans)
