백준 15686 : 치킨 배달 (Python)

본문 링크

import sys
input=sys.stdin.readline
from collections import deque
from itertools import combinations

LMI=lambda:list(map(int,input().split()))
MI=lambda:map(int,input().split())
G=lambda x:[ LMI() for _ in range(x) ]
V=lambda x,y:[ [False]*y for _ in range(x) ]

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

def BFS(select):
    copy_graph=[ i[:] for i in select_graph]
    Q=deque()
    for x,y in select:
        copy_graph[x][y]=2
        Q.append([x,y])

    visit=[ [0]*N for _ in range(N) ]
    while Q:
        x,y=Q.popleft()

        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]

            if 0<=nx<N and 0<=ny<N and copy_graph[nx][ny]!=2 and not visit[nx][ny]:
                visit[nx][ny]=visit[x][y]+1
                Q.append([nx,ny])

    total = 0
    for x,y in check:
        total+=visit[x][y]
    return total

N,M=MI()
graph=G(N)

chicken=[] ; Q=deque() ; check=[]

select_graph=[ [0]*N for _ in range(N) ]
for i in range(N):
    for j in range(N):
        if graph[i][j]==2:
            chicken.append((i,j))
        elif graph[i][j]==1:
            check.append([i,j])
            select_graph[i][j]=1


ans=int(1e9)
for i in combinations(chicken , M):
    ans=min(ans,BFS(i))

print(ans)

📌 어떻게 풀것인가?

$combination$ 과 $BFS$ 를 통해 풀었습니다.

for i in range(N):
    for j in range(N):
        if graph[i][j]==2:
            chicken.append((i,j))
        elif graph[i][j]==1:
            check.append([i,j])
            select_graph[i][j]=1

chicken 리스트에서 치킨의 위치에 대한 좌표값을 모두 넣어주었습니다. 그리고 $combination$ 을 사용해서 치킨의 지점 개수에서 $M$ 개를 뽑았습니다. 최대 $M$ 개 까지 뽑을 수 있지만 바로 $M$ 개를 뽑아도 무관합니다.

check 리스트에서는 집에 대한 좌표를 담았고 select_graph 는 집과 빈칸만 있도록 그래프를 구성했습니다.

def BFS(select):
    copy_graph=[ i[:] for i in select_graph]
    Q=deque()
    for x,y in select:
        copy_graph[x][y]=2
        Q.append([x,y])

$BFS$ 의 파라미터인 $select$ 는 이전에 $combination$ 으로 뽑은 치킨집의 좌표를 담은 배열입니다. copy_graph 배열에 0 과 1 만 담긴 select_graph 를 복새하주고 치킨의 좌표를 넣었습니다. 따라서 copy_graph 는 $M$ 개의 치킨점을 뽑았을때의 그래프가 됩니다.

또한 $BFS$ 에서 시작점이 여러곳일 경우 처음에 $Q$ 덱에 시작점을 전부 넣어주었습니다. 이 부분은 시작점이 여러점인 문제인 토마토 문제에서 아이디어를 떠올랐습니다.

while Q:
    x, y = Q.popleft()
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < N and 0 <= ny < N and copy_graph[nx][ny] != 2 and not visit[nx][ny]:
            visit[nx][ny] = visit[x][y] + 1
            Q.append([nx, ny])

이후 시작점이 여러개인 $Q$ 에서 $BFS$ 탐색을 해줍니다.

total = 0
for x, y in check:
    total += visit[x][y]
return total

이전에 check 변수에 집에 대한 정보를 넣어주었는데 , $BFS$ 탐색을 하면서 도달한 집에서의 최단경로를 전부 total 변수에 더해주었습니다.

ans=int(1e9)
for i in combinations(chicken , M):
    ans=min(ans,BFS(i))
print(ans)

ans 변수를 통해서 $BFS$ 의 값과 자기자신중 최소값을 선택하고 ans 를 출력하면 정답이 됩니다.