본문으로 바로가기

[백준 15686] 치킨 배달

category 알고리즘/백준 알고리즘 2018. 4. 16. 23:24
글에 개요

백준 알고리즘 15686번 "치킨 배달" 문제입니다.
삼성 SW 역량 테스트의 기출 문제입니다.
4월 15일 삼성전자 CE/IM 직군 2번 문제였습니다.
기본적인 문제지만 시간 초과라는 이슈에 걸릴 수 있기 때문에 java보단 c++로 알고리즘을 짜는게 좋다는 생각을 하였습니다.

[백준 15686] 주사위 굴리기 : https://www.acmicpc.net/problem/15686

참고할 글
  1. [완전탐색] http://brenden.tistory.com/10
  2. [DFS] : http://brenden.tistory.com/13
  3. [BFS] : http://brenden.tistory.com/14
핵심 내용
  1. 모든 순열을 활용하는 문제입니다.
  2. 시간 초과 이슈를 줄이기 위한 노력이 중요합니다.
해결 방법
  1. 치킨 가게와 사람 위치에 대한 좌표 값을 가지고 있는 리스트를 만듭니다.
  2. 치킨 가게 중 m개를 뽑은 후 손님 기준으로 가장 가까운 위치를 찾는다.
  3. 거리를 계산한다.
해결한 코드



백준 내용 참고


시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초512 MB41219611945.769%

문제

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

이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.

임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.

예를 들어, 아래와 같은 지도를 갖는 도시를 살펴보자.

0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 1 2

0은 빈 칸, 1은 집, 2는 치킨집이다.

(2, 1)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |2-1| + |1-2| = 2, (5, 5)에 있는 치킨집과의 거리는 |2-5| + |1-5| = 7이다. 따라서, (2, 1)에 있는 집의 치킨 거리는 2이다.

(5, 4)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |5-1| + |4-2| = 7, (5, 5)에 있는 치킨집과의 거리는 |5-5| + |4-5| = 1이다. 따라서, (2, 1)에 있는 집의 치킨 거리는 1이다.

이 도시에 있는 치킨집은 모두 같은 프랜차이즈이다. 프렌차이즈 본사에서는 수익을 증가시키기 위해 일부 치킨집을 폐업시키려고 한다. 오랜 연구 끝에 이 도시에서 가장 수익을 많이 낼 수 있는  치킨집의 개수는 최대 M개라는 사실을 알아내었다.

도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.

둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다.

도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.

출력

첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최소값을 출력한다.

예제 입력 1 

5 3
0 0 1 0 0
0 0 2 0 1
0 1 2 0 0
0 0 1 0 0
0 0 0 0 2

예제 출력 1 

5

예제 입력 2 

5 2
0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
2 0 0 1 1
2 2 0 1 2

예제 출력 2 

10

예제 입력 3 

5 1
1 2 0 0 0
1 2 0 0 0
1 2 0 0 0
1 2 0 0 0
1 2 0 0 0

예제 출력 3 

11

예제 입력 4 

5 1
1 2 0 2 1
1 2 0 2 1
1 2 0 2 1
1 2 0 2 1
1 2 0 2 1

예제 출력 4 

32



댓글을 달아 주세요

  1. jun_c 2018.04.18 18:01

    안녕하세요!
    혹시 최대 M이라는 부분 때문에, 치킨집의 갯수를 1,2,3,4,...,m인 경우 모두 살펴봐야하지 않나요?
    자바의 경우는 dfs로는 시간초과 때문에 풀지 못하는 것일까요?

    • 브랜든 홍 신고">2018.04.18 19:52 신고

      조건 없이 DFS를 하면 치킨 집 M개를 모두 탐색하는 과정에서 시간 초과가 날 수 있어요.
      그래서 위처럼 풀어야 해결되더라구요~
      [치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.]라는 조건도 있어서 시간 안에 들어올 수 있구요!!

      이 문제 C++로도 풀었었는데 속도 차이가 상당히 많이 나긴했어요... 속도 이슈 때문에 고민이 있으시다면 C++ 강력추천드립니다..

  2. 이상욱 2018.05.16 09:11

    안녕하세요!
    삼성 역량 테스트 코딩 문제 풀어보다가 이 블로그를 알게되었습니다. 블로그를 보게되다가 브랜든 홍님이 실무자 인지 궁금하게 되어서 글 남기고 갑니다ㅎㅎ

  3. 오탁종 2018.06.01 00:01

    안녕하세요
    자바를 이용한 치킨배달 문제해결방법을 분석하다가 check[]의 사용의도를 잘모르겠습니다..
    dfs를 이용해서 치킨집을 선택하고 최소거리를 구하는 큰 틀은 이해가 가고 check가 치킨집을 선택하기 위한 배열임도 알긴하는데
    알고리즘상에서 check가 굳이 필요한가 생각이 듭니다 ㅠ