[백준15686&파이썬] 조합을 이용해 브루트포스(완전탐색)해결하기

# 문제

파이썬 15686 치킨배달 파이썬 풀이

15686번: 치킨 배달

# 코드

import sys
from itertools import combinations

board = list()
N, M = map(int, sys.stdin.readline().split())
houses = list()
chicken = list()

def print2D(arr):
  for i in range(len(arr)):
    for j in range(len(arr[i])):
      print(arr[i][j], end=" ")
    print()

# 조합의 문제이다.
# 치킨집 m개에 대해서 mC1 , mC2 , mC3 .... 해가면서 최솟값을 찾는다.
  # 이런문제에서 치킨집과 집을 다른 배열에 담는거와 같은 생각을 해볼 수 있다.
for _ in range(N):
  line = list(map(int, sys.stdin.readline().split()))
  board.append(line)

for row in range(N) :
  for col in range(N) :
    if board[row][col] == 1 :
      houses.append((row,col))
    if board[row][col] == 2 :
      chicken.append((row,col))

# print(chicken)
minumum = float('inf')
# 치킨집을 조합을 통하여 뽑는다 1가지, 2가지, 3가지,,, 최대 M가지
# 집은 치킨집 하나만 선택하면 되니까 집이 먼저 돈다
for i in range(1,M+1) :
  for combi in combinations(chicken,i) :
    # print(combi) # 치킨집의 조합이 뽑힌다. 이걸 토대로 최소거리를 구하자.
    sum = 0
    for house_pos in houses :
      mmin = float('inf')
      for chicken_pos in combi :
        mmin = min(mmin,abs(house_pos[0]-chicken_pos[0]) + abs(house_pos[1]-chicken_pos[1])) # 가장 가까운 치킨집 찾기
      # 해당집에 가장 가까운 치킨집을 찾았다면 sum에 더하기
      sum += mmin
    minumum = min(minumum,sum)
print(minumum)

## 시도했지만 실패한 코드

# BFS로 각 치킨집에서 해당집으로까지의 거리를 구한다.

dirs = [
  (-1, 0), (0, 1), (1, 0), (0, -1)
  ]

distances = list()
for row in range(N):
  for col in range(N):
    if board[row][col] == 2:  # 치킨집이면 시작하기
      visit = [[False] * N for _ in range(N)]
      visit[row][col] = True  # 출발지점
      dq = deque()
      dq.append((row, col, 0))  # row,col,이동거리
      distance = list()
      while len(dq) != 0:
        cur = dq.popleft()
        for dir in dirs:
          next = (cur[0] + dir[0], cur[1] + dir[1], cur[2] + 1)
          if 0 <= next[0] < N and 0 <= next[1] < N and visit[next[0]][next[1]] == False:  # 이동가능하고 방문가능한 곳이면
            if board[next[0]][next[1]] == 1:  # 집이 있는 곳이면
              visit[next[0]][next[1]] = True
              distance.append(next)
            else:  # 치킨집(2) 이나 0 이 있는 곳
              visit[next[0]][next[1]] = True
            dq.append(next)
      distances.append(distance)


for distance in distances :
  distance.sort(key=lambda x : (x[0],x[1]))
print2D(distances)

disvisit = [False] * (len(distances))
# 얻어낸 distances를 이용해서 조합으로 최적의 값을 구하자.

 

# 풀이

## 실패했던 접근

• 맨처음 접근했던 방식은, 치킨집에서부터 시작해서 각 집까지의 경로를 distances 2차원 배열을 만들어 넣어둔다음에, (row,col)좌표에 맞게 정렬했다. 
• distances배열은 각행은 치킨집이고, 각열은 (row,col,치킨집에서 해당열(집)까지 거리)를 뜻 하게 했다.
• 그 다음 조합을 이용해서 만족하는 최소 값을 구하려고 접근했다. 
• distances 배열까지 알맞게 만들었고 조합을 사용하려 했으나, 조합을 어떤식으로 만들어야할지 몰라서 찾아 봤다.
• 맨해튼 거리를 이용한다면 굳이 힘들게 BFS와 distances배열을 만들어 탐색하지 않아도 됐기 때문에 해당 풀이 방법을 포기했다.

## 성공한 접근

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

• 지금까지 위와 같은 입력이 주어지는 문제는 board에 넣어 두고 반복문을 따로 두번 돌려서 시작점을 찾고 그 시작점에서 문제를 해결하는 코드를 반복적이게 돌리는 방법을 사용했었다. 
• 그러나 이번 문제는 치킨집(2)와 가정집(1)을 각기 다른 배열에 담아두고, 이 정보만을 이용해서 치킨집과 가정집까지의 거리를 구할 수 있었다. ( 절대값 거리 맨허튼 거리를 이용한다 )
• 그렇기 때문에 치킨이집이 가능한 모든 조합을 고른다. 1Cm , 2Cm , 3Cm ... mCm

from itertools import combinations


for i in range(1,M+1)
	for combi in combinations(chicken,i) :
		print(combi)

• 조합을 고를때는 위와 같이 combinations모듈을 사용하면 됐다. 치킨집 배열에서 i가지의 조합을 뽑아서 combi로 반환했다.
• 가정집은 가장 가까운 치킨집하나만 고르면 됐기 때문에 for문을 이용해 집을 하나 선택하고, 해당 집에서 가장 가까운 치킨집(조합에서 고른)을 확정 짓는다.
• 반복문을 돌리며 뽑히는 조합에서의 도시의치킨 거리의 최소합을 계속 갱신해나간다.

 

# 메모

• 틀에 박힌 사고를 너무 하고 있었다.
• 조합을 구하는 상황이 종종 나오는거 같은데, 조합을 다루는 방법에 대해서 공부해야겠다. N과M시리즈를 풀어볼 생각이다.