HelloMinchan
처음처럼
HelloMinchan
LinkedIn
전체 방문자
오늘
어제
  • 분류 전체보기 (306)
    • Backend (4)
      • NestJS (1)
      • Express (1)
      • Spring (2)
    • Infrastructure (1)
      • AWS (1)
    • Frontend (1)
      • Next.js (1)
    • Language & Runtime (4)
      • Java (2)
      • Node.js (2)
    • Computer Science (8)
      • Computer Networks (3)
      • Operating Systems (4)
      • OOP (1)
    • 독서 (4)
      • 데이터 중심 애플리케이션 설계 (3)
      • 객체지향의 사실과 오해 (1)
    • 회고 (4)
      • Project (2)
      • Career (2)
    • Deprecated (280)

채널

  • GitHub
  • LinkedIn

최근 글

태그

  • 프로그래머스
  • 백준Go
  • back-end
  • 백준
  • 백준C++
  • 알고스팟
  • 백준Python
  • programmers
  • 개발자
  • front-end
  • Algospot
  • 프로그래머스Python
  • Baekjoon Online Judge
  • 프로그래밍
  • 코딩
  • 알고스팟Python
  • 프로그래머스C++
  • Database
  • 데이터베이스
  • 백엔드

최근 댓글

인기 글

hELLO
HelloMinchan

처음처럼

[Baekjoon Online Judge] 백준 15686번 치킨 배달(Python)
Deprecated

[Baekjoon Online Judge] 백준 15686번 치킨 배달(Python)

2020. 3. 28. 01:16

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 15686번 치킨 배달

(Python)

(글쓴날 : 2020.03.28)

 


* Baekjoon Online Judge, 백준 15686번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.


 

 

백준 15686번 치킨 배달


1) 문제

문제 링크 : https://www.acmicpc.net/problem/15686

 

15686번: 치킨 배달

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는

www.acmicpc.net


2) 풀이 과정

2차원 배열의 인덱스 값이 0일 때 빈칸, 1일 때 집, 2일 때 치킨집이라 쳤을 때, 모든 집에서 가장 가까운 치킨집까지의 거리의 합을 구하는 문제입니다.

사실상, 1과 2가 표시되어 있는 좌표평면에서 모든 1을 기준으로 2까지의 거리의 합이 최소인 경우를 구하는 문제이며 주의해야 할 점은 치킨집 즉, 2의 개수를 문제에서 재 지정해 주므로 2가 있을 수 있는 위치의 조합을 계산해 1과의 최소 거리를 구해야 합니다.

 

저의 경우, 모든 집의 위치와 치킨집의 위치를 먼저 구해놓은 뒤, 치킨집의 개수에 따른 조합을 구했고,

모든 조합의 경우에서 집을 기준으로 치킨집까지의 최소 거리의 합들을 solution 리스트에 저장했습니다.

그 후 min() 함수를 사용해 모든 조합의 경우 중 최소 거리의 합이 가장 작은 값을 구해 문제를 해결했습니다.


3) 코드

 

* Python 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import sys
input = sys.stdin.readline
from itertools import combinations as C
 
N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
allHouse = []
allChicken = []
 
for i in range(N):
    for j in range(N):
        if arr[i][j] == 1:
            allHouse.append((i, j))
        elif arr[i][j] == 2:
            allChicken.append((i, j))
 
allAliveChickenList = list(C(allChicken, M))
 
solution = []
for aliveChickenList in allAliveChickenList:
    allDistance = 0
    for house in allHouse:
        distance = 9999
        for chickenX, chickenY in aliveChickenList:
            if distance > abs(house[0] - chickenX) + abs(house[1] - chickenY):
                distance = abs(house[0] - chickenX) + abs(house[1] - chickenY)
        allDistance += distance
    solution.append(allDistance)
 
print(min(solution))

 

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

'Deprecated' 카테고리의 다른 글

[Baekjoon Online Judge] 백준 15649번 N과 M (1)(Python)  (0) 2020.03.28
[Baekjoon Online Judge] 백준 2667번 단지번호붙이기(Python)  (0) 2020.03.28
[Amazon Web Services] EC2 인스턴스에 PuTTY로 접속하는 법  (0) 2020.03.27
[Baekjoon Online Judge] 백준 14889번 스타트와 링크(Python)  (0) 2020.03.27
[Baekjoon Online Judge] 백준 1182번 부분수열의 합(Python)  (0) 2020.03.25
    'Deprecated' 카테고리의 다른 글
    • [Baekjoon Online Judge] 백준 15649번 N과 M (1)(Python)
    • [Baekjoon Online Judge] 백준 2667번 단지번호붙이기(Python)
    • [Amazon Web Services] EC2 인스턴스에 PuTTY로 접속하는 법
    • [Baekjoon Online Judge] 백준 14889번 스타트와 링크(Python)
    HelloMinchan
    HelloMinchan
    Though you should not fear failure, You should do your very best to avoid it.

    티스토리툴바