Notice
Recent Posts
Recent Comments
Link
코딩 공부
[Python](구현, 조합) 백준 15685번 : 치킨 배달 본문
728x90
<접근 방법>
- 집과 치킨집 사이의 거리를 구해야하므로
집(arr[i][j] == 1)과 치킨집(arr[i][j] == 2)의 좌표를 각각 loc_house, loc_chicken 리스트에 저장한다.예제 2의 house들의 좌표와 chicken집들의 좌표 - distance라는 이차원 배열을 만들어서 행과 열은 각각 집과 치킨집을 나타내도록 하고 서로의 거리를 구한다.
3. 조합의 결과로 나올 수 있는 치킨집의 경우의 수를 구해
각 집들에 있어 살아남은 치킨집들까지의 최소 거리(temp)를 total에 더한다.
4. 하나의 조합의 결과가 total이고, 우리가 구하고자 하는 정답은 answer, 즉 조합들의 결과 중 가장 최소인 값을 구하는 것
이 목표이므로 answer = min(answer, total)로 정답을 갱신해준다.
from itertools import combinations
N, M = map(int, input().split()) # NxN 도시, M:남길 치킨집 개수
arr = [list(map(int, input().split())) for _ in range(N)]
loc_house = [] # 집들의 좌표를 담을 리스트
loc_chicken = [] # 치킨집들의 좌표를 담을 리스트
for i in range(N):
for j in range(N):
if arr[i][j] == 1:
loc_house.append((i, j))
elif arr[i][j] == 2:
loc_chicken.append((i, j))
# 집들과 치킨집들 간의 각각의 거리를 distance라는 이차원 배열로 만들기
distance = [[0]*len(loc_chicken) for _ in range(len(loc_house))]
for i in range(len(loc_house)):
for j in range(len(loc_chicken)):
distance[i][j] = abs(loc_house[i][0]-loc_chicken[j][0]) + abs(loc_house[i][1]-loc_chicken[j][1])
answer = 1e9
for rest in combinations(range(len(loc_chicken)), M):
total = 0
for i in range(len(loc_house)):
temp = 2*N # 가장 멀리 떨어져 있어도 거리가 2*N을 넘지 않으므로 2*N으로 설정
for j in rest:
if distance[i][j] < temp: # 가장 가까운 거리로 갱신
temp = distance[i][j]
total += temp # 최종적으로 갱신된 결과를 total에 합산
answer = min(total, answer) # 최소 치킨 거리로 정답을 갱신
print(answer)
이해가 안되는 부분이 있으면 질문 주세요. 감사합니다.
728x90
'삼성 SW 역량 테스트 기출 문제' 카테고리의 다른 글
[Python](시뮬) 백준 21608번 : 상어 초등학교 (2) | 2024.01.28 |
---|---|
[Python] 백준 20055번 : 컨베이어 벨트 위의 로봇 (0) | 2024.01.28 |
[Python](구현) 백준 14891번 : 톱니바퀴 (0) | 2024.01.18 |
[Python](구현) 백준 14503번 : 로봇 청소기 (0) | 2024.01.17 |
[Python](DFS) 백준 14888번 : 연산자 끼워넣기 (2) | 2024.01.16 |