[백준] 15686 치킨 배달 (파이썬 python)

2022. 3. 5. 23:17· Algorithm/BOJ

 

 

문제 링크

 

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

 

15686번: 치킨 배달

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸

www.acmicpc.net

 

 

문제

 

 

 

 

 

문제 풀이

 

 

from itertools import combinations

n, m = map(int, input().split())
chicken, house = [], []
data = []
for _ in range(n):
    data.append(list(map(int, input().split())))
result = 9999

for r in range(n):
    for c in range(n):
        if data[r][c] == 1:
            house.append((r, c))    # 일반 집
        elif data[r][c] == 2:
            chicken.append((r, c))    # 치킨집

for c in combinations(chicken, m):
    temp = 0
    for h in house:
        chicken_len = 9999
        for i in range(m):
            chicken_len = min(chicken_len, abs(h[0] - c[i][0]) + abs(h[1] - c[i][1]))
        temp += chicken_len
    result = min(result, temp)

print(result)

 

 

완전 탐색과 조합을 이용한 풀이이다.

data에 각 위치를 모두 저장한 후

값이 1일 경우 house 리스트에, 2일 경우 chicken 리스트에 위치를 저장한다.

combinations(리스트, m) => 리스트에서 m개의 조합을 뽑아준다!

조합으로 뽑힌 치킨집과 집의 치킨 거리를 찾아 최소의 값을 temp에 더해주는 연산을 모두 마친 후

이들 중 최소의 값을 출력해주면 된다 :)

 

 

저작자표시 비영리 변경금지 (새창열림)

'Algorithm > BOJ' 카테고리의 다른 글

[백준] 14889 스타트와 링크 (파이썬 python)  (0) 2022.03.08
[백준] 14888 연산자 끼워넣기 (파이썬 python)  (0) 2022.03.08
[백준] 2178 미로 탐색(파이썬 python)  (0) 2022.02.28
[백준] 14503 로봇 청소기(파이썬 python)  (0) 2022.02.24
[백준] 1476 날짜 계산 (파이썬 python)  (0) 2022.02.01
'Algorithm/BOJ' 카테고리의 다른 글
  • [백준] 14889 스타트와 링크 (파이썬 python)
  • [백준] 14888 연산자 끼워넣기 (파이썬 python)
  • [백준] 2178 미로 탐색(파이썬 python)
  • [백준] 14503 로봇 청소기(파이썬 python)
YOONJELLY
YOONJELLY
YOONJELLY
JELLYJELLY
YOONJELLY
전체
오늘
어제
  • 분류 전체보기 (153)
    • Springboot (2)
    • Android (15)
    • Algorithm (126)
      • 개념 (8)
      • BOJ (91)
      • Programmers (15)
      • SWEA (4)
    • 경험_기록 (1)
    • RIM_TIP (4)
    • Github (2)
    • CS (1)
      • 운영체제 (1)
      • 컴퓨터네트워크 (0)
      • 정보처리기사 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 프로그래머스
  • softeer
  • BOJ
  • 코틀린
  • DFS
  • Python
  • Android
  • programmers
  • 문자열
  • 완전탐색
  • 정렬
  • 이것이코딩테스트다
  • BFS
  • 큐
  • 알고리즘
  • 딕셔너리
  • 액티비티컴포넌트
  • 스택
  • SWEA
  • 자료구조
  • 백준
  • 이진탐색
  • DP
  • 코딩테스트
  • 안드로이드
  • 소프티어
  • 그리디
  • 다이나믹프로그래밍
  • 파이썬
  • kotlin

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
YOONJELLY
[백준] 15686 치킨 배달 (파이썬 python)
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.