이번 주 주제는 시뮬레이션입니다.
부끄럽지만 시뮬레이션 공부는 처음이네요~^^ 별로
https://www.acmicpc.net/problem/15686
#15686: 치킨 배달
NxN 크기의 도시가 있습니다. 도시는 1×1 정사각형으로 나뉩니다. 도시의 모든 광장은 빈 광장이거나 닭장이거나 집입니다. 도시의 셀은 r행, c열 또는 위에서 r번째 셀에 (r, c)의 형태로 표시됩니다.
www.acmicpc.net
(주요 유형)
1. 2차원 공간(위, 아래, 왼쪽, 오른쪽) 방향 벡터를 잘 활용하자.
2. 특정 게임 구현 머릿속에 테스트 케이스를 상상해 보세요.
(기능)
1. 문제 해결 그래서 이용약관을 읽고 준수하십시오.
2. 데이터 구조를 현명하게 사용하십시오.
주절… 주절… 주절…
사실 제가 이 글을 올린 이유는 시뮬레이션 문제에 대한 태도 + 좌표 다루기보고 또 본다고 해도 과언이 아닙니다.
고민하다가 생각한 해결책
1. 먼저 집의 위치를 찾습니다.
2. 치킨집까지의 거리를 찾습니다.
3. 치킨집과의 최소한의 거리를 유지하세요.
4. 모두 누적 더하면 최소 케이스가 반환됩니다.
내 뇌는 여기서 멈춘다. 아 근데 아껴야할게 엠치킨집 있는데 없애야할 치킨스트리트???
이슈를 있는 그대로 추구하는 것이 중요하다고 하셨습니다.
제거할 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치킨집 거리를 둘러봐야 하므로 세대가 바깥문이고 치킨집이 안문이다. 안쪽 문을 돌면 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. 좌표, 튜플을 다루는 방법.. 결국 꽤 자주 발생합니다..