15686 백준 파이썬

치킨집을 m개만 남기되 집과 거리가 최소가 되도록 만드는 문제

m개 남기는 것은 dfs로, 거리 체크는 bfs로 할려고 했으나 시간초과. 이 놈의 dfs는 맨날 시간초과다.

아래는 처음 작성한 코드다.

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

def delete(v):
    global ans
    if v==0:
        result=0
        for x in LIST:
            result+=bfs(x)
        ans.append(result)
        return result
    else:
        for x in range(n):
            for y in range(n):
                if space[x][y]==2:
                    space[x][y]=0
                    delete(v-1)
                    space[x][y]=2

def bfs(t):
    q=deque()
    q.append(t)
    vis=[[0 for _ in range(n)] for _ in range(n)]
    a=[1,-1,0,0]
    b=[0,0,-1,1]
    while q:
        x,y,cnt=q.popleft()
        vis[x][y]=1
        for i in range(4):
            X=x+a[i]
            Y=y+b[i]
            if 0<=X<n and 0<=Y<n: 
                if (space[X][Y]==1 or space[X][Y]==0) and vis[X][Y]==0:
                    q.append([X,Y,cnt+1])
                elif space[X][Y]==2:
                    return cnt+1


n,m=map(int,input().split())
space=[]
ans=[]
for x in range(n):
    tmp=list(map(int,input().split()))
    space.append(tmp)
plus=0
LIST=[]
for x in range(n):
    for y in range(n):
        if space[x][y]==2:
            plus+=1
        if space[x][y]==1:
            LIST.append([x,y,0])
v=plus-m
delete(v)
print(min(ans))

 

하지만 이건 굳이 dfs로 안해도 조합을 통해서 해결 할 수 있다. 왜냐면 실제로 치킨집을 리스트 상에서 기록해 주지 않아도 되기 때문이다.

from itertools import combinations

n,m=map(int, input().split())
maps=[]
for i in range(n):
  maps.append(list(map(int, input().split())))

home=[]
chicken=[]
for i in range(n):
  for j in range(n):
    if maps[i][j]==1:
      home.append((i,j))
    elif maps[i][j]==2:
      chicken.append((i,j))

pick_chicken=list(combinations(chicken,m))
result=[0]*len(pick_chicken)

for i in home:
  for j in range(len(pick_chicken)):
    a=99999
    for k in pick_chicken[j]:
      temp=abs(i[0]-k[0])+abs(i[1]-k[1])
      a=min(a,temp)
    result[j]+=a

print(min(result))

1. 집 좌표와 치킨집 좌표 저장

2. 치킨집중 m개를 골라 조합으로 pcik_chicken에 저장

3. 집 반복문 내에서 pick_chicken을 순차적으로 진행시키며 거리를 구해 최소값 a에 저장

4. a의 합 result에 저장

5. result 출력