183. 치킨 배달

1) 어떤 전략(알고리즘)으로 해결?

bfs를 활용한 완전 탐색이지
위의 생각에 사로잡혀서 삽질 대마왕함, 그냥 단순하게 조합 경우만 구해서 그 때의 치킨 거리 구해주면 끝인 문제였던 것임

2) 코딩 설명

• 조합으로 치킨집 뽑는 경우의 수 구하기
• 그 경우의 수 때마다 치킨 거리 구해서 total list에 넣기
• 경우의 수 for 문 마무리되면 total list에서 최솟값이 가장 짧은 치킨거리 경우의 수

<내 풀이>

from collections import deque
from itertools import combinations
import sys

r = [0, 0, -1 , 1]
c = [-1, 1, 0, 0]

n, m = map(int,sys.stdin.readline().rstrip().split())
# 크기가 N×N인 도시
# 첫째 줄에 폐업시키지 않을 치킨집을 최대 M개

map = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
# 0은 빈 칸, 1은 집, 2는 치킨집

chkn =[]
for i in range(n) :
    for j in range(n) :
        if map[i][j]==2 :
            chkn.append((i,j))

comb = list(combinations(chkn, m))

# 5 2
# [((0, 1), (3, 0)), ((0, 1), (4, 0)),  치킨 하우스의 리스트 
# ((0, 1), (4, 1)), ((0, 1), (4, 4)), 
# ((3, 0), (4, 0)), ((3, 0), (4, 1)), 
# ((3, 0), (4, 4)), ((4, 0), (4, 1)), 
# ((4, 0), (4, 4)), ((4, 1), (4, 4))]

total_chck_list=[]
min_dis = 0
for j in range(len(comb)) : #각 경우의 수를 돌아주기 
    current_chk_dis = 0 # `현재 경우의 치킨 거리`
    chk_list = comb[j] #현재 골랐다고 가정하는 치킨 하우스의 리스트 

    for i in range(n) :
        for j in range(n)  :
            if map[i][j] == 1 : # 집이라면
                min_dis = 99999

                for k in chk_list :
                    cmp_dis = abs(i-k[0]) + abs(j-k[1])

                    if cmp_dis < min_dis :
                    
                        min_dis = cmp_dis

            # 한 집 검사 끝나면 치킨 거리를 `현재 경우의 치킨 거리` 에 더하기
                current_chk_dis+= min_dis
                #print("home", min_dis)
            


    # 한 경우의 수 끝나면 치킨 거리를 total 리스트에 더하기 
    total_chck_list.append(current_chk_dis)

# print(total_chck_list)
print(min(total_chck_list))

<다른 분의 풀이 or 내 틀렸던 풀이, 문제점>

출처 : 출처

1) 문제잘못 이해

from collections import deque
import sys

def bfs(q, dis, current_chkicken_row,  current_chkicken_col) :
    global chick_distance
    while q : 
        print("q, ", q)
        now = q.popleft() # (r,c)
        for i in range(4) : # 상하좌우 살펴보기
            tmpr = r[i] + now[0]
            tmpc = c[i] + now[1]

            if (tmpr < n) and (tmpc < n) and \
                    dis[tmpr][tmpc] == 0 :

                dis[tmpr][tmpc] = dis[now[0]][now[1]] + 1
                q.append((tmpr, tmpc))
                print("qq", q)
                print(tmpr, tmpc , map[tmpr][tmpc])
                for i in dis :
                    print("dis", i)
                if map[tmpr][tmpc] == 1 : #집 발견하면 현재 치킨집과 거리 계산 
                    print("home ", tmpr, tmpc)
                    chick_distance+= abs(current_chkicken_row-tmpr) + \
                    abs(current_chkicken_col - now[1]-tmpc)

r = [0, 0, -1 , 1]
c = [-1, 1, 0, 0]

n, m = map(int,sys.stdin.readline().rstrip().split())
# 크기가 N×N인 도시
# 첫째 줄에 폐업시키지 않을 치킨집을 최대 M개

map = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
# 0은 빈 칸, 1은 집, 2는 치킨집

home = []
chickdis_list = []

for i in range(n) :
    for j in range(n)  :

        if map[i][j]==2 : #치킨집 발견하면 치킨집을 시작점 

            dis = [[0]*(n) for _ in range(n)]

            dis[i][j] = 0

            q=deque()
            q.append((i,j))

            chick_distance = 0
            print(i, j)
            
            bfs(q, dis, i,j)
            chickdis_list.append(chick_distance)

            print('\n')
            
chickdis_list.sort()

# 도시의 치킨 거리의 최솟값
print(chickdis_list[:m])
print(sum(chickdis_list[:m]))

2) 답은 맞는데,, 시간초과 => 접근을 잘못한거였음ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

from collections import deque
from itertools import combinations
import sys

def bfs(map, q, dis, home_row,  home_col) :
    global mini_distance
    while q : 
        now = q.popleft() # (r,c)
        for i in range(4) : # 상하좌우 살펴보기
            tmpr = r[i] + now[0]
            tmpc = c[i] + now[1]

            if (0<= tmpr < n) and (0<=tmpc < n) and \
                    dis[tmpr][tmpc] == 0 :

                dis[tmpr][tmpc] = dis[now[0]][now[1]] + 1
                q.append((tmpr, tmpc))

                if map[tmpr][tmpc] == 3 : # 치킨집 발견 시 현재 치킨집과 거리 계산 
                    
                    chick_distance = abs(home_row-tmpr) + \
                    abs(home_col -tmpc)

                    if chick_distance < mini_distance : 
                        # print("ch", tmpr, tmpc)
                        # print("home", home_row, home_col)
                        # print("chkick", chick_distance)
                        mini_distance = chick_distance

r = [0, 0, -1 , 1]
c = [-1, 1, 0, 0]

n, m = map(int,sys.stdin.readline().rstrip().split())
# 크기가 N×N인 도시
# 첫째 줄에 폐업시키지 않을 치킨집을 최대 M개

map = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
# 0은 빈 칸, 1은 집, 2는 치킨집

chkn =[]
for i in range(n) :
    for j in range(n) :
        if map[i][j]==2 :
            chkn.append((i,j))

comb = list(combinations(chkn, m))

# 5 2
# [((0, 1), (3, 0)), ((0, 1), (4, 0)), 
# ((0, 1), (4, 1)), ((0, 1), (4, 4)), 
# ((3, 0), (4, 0)), ((3, 0), (4, 1)), 
# ((3, 0), (4, 4)), ((4, 0), (4, 1)), 
# ((4, 0), (4, 4)), ((4, 1), (4, 4))]

total_chck_list=[]

for j in range(len(comb)) :

    tmpmap = map.copy()
    chickdis_list = []

    for k in comb[j] :
        tmpmap[k[0]][k[1]] = 3

    for i in range(n) :
        for j in range(n)  :

            if map[i][j]==1 : #집 발견하면 집을 시작점 

                dis = [[0]*(n) for _ in range(n)]
                dis[i][j] = 1

                q=deque()
                q.append((i,j))

                mini_distance = 999
                
                bfs(tmpmap, q, dis, i,j)
                chickdis_list.append(mini_distance)

    chickdis_list.sort()

    total_chck_list.append(sum(chickdis_list))
    tmpmap[k[0]][k[1]] = 2 #아까 변환해둔 3을 2로 되돌려주기 

# print(total_chck_list)
print(min(total_chck_list))

아 굳이 BFS 로 풀 필요없자나;;

최단거리 문제 아니자나,, ㅠㅠ

• 걍 경우의 수만 고려하면 되쟈냐

<반성 점>

• 너무 자만? 설렁설렁 문제를 읽고 뭔가 가장 짧은 거리라는 말에 bfs로 괜히 접근함 ;; 그럴 필요 전혀없었는데 말이다~

<배운 점>

• 문제를 꼼꼼히 읽고 접근 방법을 정해야 한다.