[BOJ] 치킨배달 (15686)

[문제]

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

15686번: 치킨 배달

 

---

 

[풀이]

문제를 처음 읽었을 때 BFS를 통해 풀어야겠다고 생각했는데 그이유는 다음 두 가지다.

1. 집과 치킨집 사이의 최단거리라는 워딩이 주어짐
2. 주어지는 지도 정보가 2차원 배열 형태

 

BFS로 풀기로 정하고 세운 계획은 다음과 같다.

1. 지도 정보를 2차원 리스트에 저장한다.
2. 모든 치킨집 좌표 중 M개만 선택하는 조합을 생성한다.
3. 지도 정보를 복사한다.
4. 조합을 사용하여 복사한 지도 정보에서 M개의 치킨집만 남기고 모두 제거한다.
5. 복사한 지도를 선형으로 탐색하다가 집을 만나면 해당 집에서 부터 BFS를 수행하여 가장 가까운 치킨집을 찾고 그 거리가 치킨 거리가 된다.
6. 모든 집들에 대해 치킨거리를 계산하여 그 합을 구하면 치킨집 중 M개를 선택한 조합 요소에 대한 치킨거리의 합이 된다.
7. 치킨집을 M개씩 선택한 모든 조합요소별로 치킨거리 합을 구하고 그 가운데 가장 작은 값을 구하면 우리가 얻고자 하는 답이 된다.

 

세운 계획을 바탕으로 작성한 코드는 다음과 같다.

import sys
from collections import deque
from itertools import combinations
from copy import deepcopy


def bfs(new_map_info, s_pos):
    # direction vectors: 상, 우, 하, 좌
    dy = [-1, 0, 1, 0]
    dx = [0, 1, 0, -1]
    max_idx = len(new_map_info) - 1

    # 새로운 집을 발견 할 때마다 큐와 방문내역을 초기화 한다.
    queue = deque(list())
    visited = [[0] * (N + 1) for _ in range(N + 1)]

    # 탐색 진입 점을 큐에 넣어준다.
    queue.append(s_pos)
    # 진입 지점 방문 처리
    visited[s_pos[0]][s_pos[1]] = 1

    # 큐가 비워질 때까지 혹은 치킨 집을 찾을 때까지 반복
    while queue:
        c_pos = queue.popleft()

        for i in range(4):
            n_pos = (c_pos[0] + dy[i], c_pos[1] + dx[i])
            if 0 < n_pos[0] <= max_idx and 0 < n_pos[1] <= max_idx:
                # 치킨 집이면 탐색 종료하고 마지막 방문 지점을 리턴
                if new_map_info[n_pos[0]][n_pos[1]] == 2:
                    return n_pos
                # 치킨집 못찾으면 계속 BFS 진행. 집이든 빈칸이든 가리지 않고 방문 처리
                visited[n_pos[0]][n_pos[1]] = 1
                queue.append(n_pos)


N, M = map(int, sys.stdin.readline().rstrip().split())
map_info = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    for j, m in enumerate(map(int, sys.stdin.readline().rstrip().split()), 1):
        map_info[i][j] = m

all_c_pos = set()  # All of chicken positions
for r in range(1, N + 1):
    for c in range(1, N + 1):
        if map_info[r][c] == 2:
            all_c_pos.add((r, c))

c_p_comb = combinations(all_c_pos, M)   # chicken position set by M

a_c_dists = []  # 치킨가게 조합 별로 각 집으로 부터의 치킨거리를 누적한 값들을 저장해 놓을 리스트
for el in c_p_comb:
    closed_c_pos = all_c_pos.difference(set(el))    # 폐점한 치킨 집
    new_map_info = deepcopy(map_info)

    for ccp in closed_c_pos:
        new_map_info[ccp[0]][ccp[1]] = 0    # 폐점한 치킨 집을 맵에서 제거

    acc_c_dist = 0    # 누적 치킨거리
    for r in range(1, N + 1):
        for c in range(1, N + 1):
            # 집을 찾아서 BFS로 최단거리의 치킨집을 탐색
            if new_map_info[r][c] == 1:
                chk_pos = bfs(new_map_info, (r, c))   # 치킨집 위치를 찾았다.
                # 현재위치를 고려하여 치킨거리를 구해서 누적 치킨거리에 더해준다.
                acc_c_dist += abs(r - chk_pos[0]) + abs(c - chk_pos[1])
    a_c_dists.append(acc_c_dist)

print(min(a_c_dists))

 

실행결과 예시의 테스트 케이스는 잘 통과 했지만 제출 시 시간초과 판정을 받았다.

 

사실 위의 코드를 작성하면서 의아했던 것은 BFS를 돌면서 첫번 째 치킨집을 만날 때까지 카운트를 증가시키면 치킨거리를 구할 수 있는데 왜 집과 치킨집 사이의 거리를 구하는 공식을 명시적으로 알려줬을까 였다.

 

그에 대한 답은 문제에 있었는데 치킨 집은 13개 까지만 남길 수 있으므로  13개의 치킨집과 모든 집의 좌표 간에 치킨거리를 완전탐색으로 계산해도 큰 무리가 없을 것으로 판단되었다.

 

---

 

[개선]

BFS를 사용하지 않고 집과 치킨집 사이의 치킨거리를 완전탐색으로 구하여 문제를 해결하도록 해보자.

 

1. 주어진 맵정보에서 치킨집의 좌표들과 집의 좌표들을 각각 추출하도록 한다.
2. 치킨집 좌표에서 M개를 선택하는 조합을 만든다.
3. 각 조합 요소는 M개의 치킨집 좌표이다. 모든 조합요소들에 대해 다음의 로직을 실행한다.
   1. 각 집에서 부터의 치킨거리를 확인한다.
   2. 모든 집의 치킨거리를 합한다.
4. 3을 통해 구해진 조합 요소별 치킨거리 합 가운데 가장 작은 값이 구하고자 하는 답이 된다.

이를 코드로 옮겨보면 다음과 같다.

import sys
from itertools import combinations as comb
f_input = sys.stdin.readline
# N: map size
# M: number of chicken joints
N, M = map(int, f_input().split())
cj_pos = set()
h_pos = set()
for r in range(1, N + 1):
    for c, map_info in enumerate(map(int, f_input().split()), 1):
        if map_info == 2:
            cj_pos.add((r, c))
        elif map_info == 1:
            h_pos.add((r, c))

ans = int(1e9)
for cj_comb in comb(cj_pos, M):
    c_dist = 0
    for h in h_pos:
        shortest_dist = int(1e9)
        for cj in cj_comb:
            if shortest_dist > abs(h[0] - cj[0]) + abs(h[1] - cj[1]):
                shortest_dist = abs(h[0] - cj[0]) + abs(h[1] - cj[1])
        c_dist += shortest_dist
    if ans > c_dist:
        ans = c_dist

print(ans)

 

항상 느끼는 것인데, 문제를 풀 때는 절대 기계적으로 접근하면 안된다. 입력과 실행되는 로직을 통해 대략적인 시간복잡도를 생각하면서 풀어야 효율적으로 풀 수 있다.