[Python][구현/BFS/조합] 치킨 배달 - 백준 15686번, 삼성 기출 문제

[문제]

 

[알고리즘]

• BFS, 조합의 문제이다.
• 입력 받은 치킨의 개수(M보다 크거나 같다) 중 선택할 치킨 M개를 선택한다. 
  • 백트래킹 방식을 사용한다.
• BFS로 치킨집으로부터 각 집까지의 거리를 계산한다.

 

[느낀 점 / 깨달은 점]

• 어제 풀었던 바이러스연구소 문제와 비슷하여 풀어보았다.
• test case의 정답은 다 맞았지만, 자꾸만 채점 1%에서 틀렸습니다 결과가 나왔다.
  • 오류를 찾기 어려웠지만 찬찬히 코드를 본 결과, 백트래킹 부분에서 코딩 실수가 나왔다.
  • 아래 코드의 jj를 j로 잘못 쓴 코딩 실수였다. 
• 조합을 풀 때 조심해야할 것은 현재의 위치보다 그 뒤 위치를 선택해야한다는 것이다. 
  • 나는 아래 코드와 같이 jj+1나 ii+1 처리를 해주었다. 이 처리를 안해주니 자꾸만 1개씩만 뽑힌 결과가 나왔다. 조심하자!

import copy 
import sys

def print_2darray(a):
    for i in a:
        for j in i:
            print(j, end=' ')
        print()
    print('--------')
    
def select_chicken(num, i, j):
    if num == M :
        # print("temp_city")
        # print_2darray(temp_city)
        bfs()
        return
    for ii in range(i, N):
        for jj in range(j, N):
            if city[ii][jj] == 2 : 
                temp_city[ii][jj] = 2
                if jj == N-1 :
                    select_chicken(num+1, ii+1, 0)
                else : 
                    select_chicken(num+1, ii, jj+1)
                temp_city[ii][jj] = 0
            j = 0

def bfs():
    from collections import deque

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

    v = [[0] * N for _ in range(N)] 

    q = deque()
    for i in range(N):
        for j in range(N):
            if temp_city[i][j] == 2 : 
                q.append([i, j])

    num = 0
    while q :
        if num == num_house : 
            break
        
        i, j = q.popleft()

        for n in range(4):
            ii = i + dy[n]
            jj = j + dx[n]

            if ii < 0 or jj < 0 or ii >= N or jj >= N or temp_city[ii][jj] == 2 :
                continue
            elif  v[ii][jj] == 0 : 
                v[ii][jj] = v[i][j] +1
                q.append([ii,jj])
                if temp_city[ii][jj] == 1 :
                    num +=1

    global answer
    dist= 0
    for i in range(N):
        for j in range(N):
            if temp_city[i][j] == 1 : 
                dist += v[i][j]
    answer = min(answer, dist)

N, M = map(int, input().split())

city = [list(map(int, input().split())) for _ in range(N)]

temp_city = copy.deepcopy(city)
answer = sys.maxsize

num_house = 0
for i in range(N):
    for j in range(N):
        if city[i][j] == 2 : 
            temp_city[i][j] = 0
        if city[i][j] == 1 : 
            num_house +=1

select_chicken(0, 0, 0)
print(answer)