[백준 15686] 치킨 배달 (Python)

www.acmicpc.net/problem/15686

15686번: 치킨 배달

 

문제풀이

N, M, board : 입력값

chicken : 치킨집 좌표 리스트

tmp_board : 치킨집이 없는 board (집과 빈 공간만 있는 2차원 리스트)

dist : 치킨집을 기준으로 최단 이동 거리

 

Combination(조합) 으로 치킨집을 M개 선택하여 BFS를 통해 각 집까지의 거리를 탐색하는 방식으로 해결할 수 있다.

 

1. Combination을 통해 M개의 치킨집 선택하기

 

2. BFS 탐색하기

- 치킨집을 기준으로 각 공간까지의 거리 계산

 

3. 치킨집에서 집까지의 거리를 모두 더하여 총 거리 계산

 

4. 1-3 과정 반복 및 최소 거리 구하기

 

코드

import sys
from itertools import combinations
from collections import deque

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def bfs(chicken):
    q = deque(chicken)
    for t in chicken:
        dist[t[0]][t[1]] = 0
    tmp = 0
    while q:
        size = len(q)
        for _ in range(size):
            x, y = q.popleft()
            for k in range(4):
                nx, ny = x + dx[k], y + dy[k]
                if 0 <= nx < N and 0 <= ny < N:
                    if tmp_board[nx][ny] != 2 and dist[nx][ny] == -1:
                        q.append((nx, ny))
                        dist[nx][ny] = dist[x][y] + 1
    for i in range(N):
        for j in range(N):
            if tmp_board[i][j] == 1:
                tmp += dist[i][j]
    return tmp

if __name__ == '__main__':
    N, M = map(int, sys.stdin.readline().split())
    board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
    chicken = []
    ans = sys.maxsize
    tmp_board = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if board[i][j] == 2: chicken.append((i, j))
            if board[i][j] == 1: tmp_board[i][j] = 1
    for c in combinations(chicken, M):
        dist = [[-1] * N for _ in range(N)]
        ans = min(ans, bfs(list(c)))
    print(ans)

 

결과

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!