[백준/15686] 치킨 배달 | 시뮬레이션 | 2차원 공간 좌표 다루기

이번주 주제는 시뮬레이션.

부끄럽지만 시뮬레이션은 처음 공부해본다~^^ 별 것 아님.

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

15686번: 치킨 배달

[주요 유형]

1. 2차원 공간(상,하,좌,우) ✅ 방향 벡터를 잘 쓰자.

2. 특정 게임 구현 ✅ 머릿속으로 상상하면서 테스트 케이스를 떠올리자.

[Skills]

1. 문제를 잘 읽고 조건을 빼먹지 않게 메모하자

2. 자료구조를 잘 활용하자.

---

주절..주절...주절....

사실 이 문제를 포스팅한 이유는 시뮬레이션 문제를 대하는 태도 + 좌표 다루는 것을 두고두고 보려고,,라고 해도 과언이 아니다.

 

열심히 머리를 꿀리면서 생각한 풀이는

1. 일단 집 위치를 찾는다.

2. 치킨집들과의 거리를 찾는다.

3. 최솟값인 치킨집 거리를 저장한다.

4. 모두 누적해서 더했을 때, 최소인 경우를 출력한다.

 

여기서 뇌정지.. 어라 근데 내가 구해야 하는 거는 없애야 하는 치킨집이 M개일 때의 치킨거리인데???

➡️ 문제 그대로 잘 따라가는 것이 중요하다고 했다.

➡️ 내가 구해야 하는 것은 없앨 치킨집이 M개일 때의 거리이기 때문에 일단 M개의 치킨집을 선택하자!

---

[알고리즘]

일단 치킨집이랑 가정집이 어디에있는지 좌표를 저장해준다.

c, h = [], []
for i in range(n) : 
    for j in range(n) : 
        if city[i][j] == 1 : h.append((i,j))
        elif city[i][j] == 2 : c.append((i,j))

 

치킨집 M개를 골라서 얘네들이 위치한 좌표들과 가정집의 좌표들을 비교하여 거리를 측정해준다. 이때 가정집 좌표 한 점에서 m개의 치킨집과의 거리를 둘러봐야 하기 때문에 가정집이 바깥 for문, 치킨집이 내부 for문이다. 안쪽 for문을 돌면 가정집 1에서부터 m개의 치킨집까지 거리를 비교하여 최소거리만 남게 된다. 이를 res에 누적하여 도시의 치킨 거리를 구한다.

chicken_m = cb(c, m)

for m in chicken_m : 
    # 고른 M개의 좌표와 home을 비교하면서 가장 가까운 c 찾기
    res = 0
    for hx, hy in h : 
        dist = float('inf')
        for cx, cy in m :
            dist = min(dist, abs(hx-cx)+abs(hy-cy))
        res += dist
    ans = min(ans,res)

 

---

[전체 코드]

from itertools import combinations as cb

n,m = map(int, input().split())
city = [list(map(int, input().split())) for _ in range(n)]
ans = float('inf')

# 치킨집, 가정집 좌표 저장
c, h = [], []
for i in range(n) : 
    for j in range(n) : 
        if city[i][j] == 1 : h.append((i,j))
        elif city[i][j] == 2 : c.append((i,j))

# 전체 c 중에 M개만 선택해야 함
chicken_m = cb(c, m)
print(list(chicken_m))
for m in chicken_m : 
    # 고른 M개의 좌표와 home을 비교하면서 가장 가까운 c 찾기
    res = 0
    for hx, hy in h : 
        dist = float('inf')
        for cx, cy in m :
            dist = min(dist, abs(hx-cx)+abs(hy-cy))
        res += dist
    ans = min(ans,res)
print(ans)

---

[알게된 점]

1. 문제를 잘!!읽고 잘!! ❗️따라가자❗️어떻게보면 풀이를 내 사고로 떠올려야 하는 다른 문제들보다 쉬운거아님?? 그대로 따라가면되니까..

2. 좌표 다루는 방법, 튜플이.. 드디어 꽤 자주.. 등장하는 중