피자 거리 배달(삼성 SW역량평가 기출문제 : DFS활용) - Python

<문제>

 

N×N 크기의 도시지도가 있습니다. 도시지도는 1×1크기의 격자칸으로 이루어져 있습니다. 각 격자칸에는 0은 빈칸, 1은 집, 2는 피자집으로 표현됩니다. 각 격자칸은 좌표(행번호, 열 번호) 로 표현됩니다. 행번호는 1번부터 N번까지이고, 열 번호도 1부터 N까지입니다.
도시에는 각 집마다 “피자배달거리”가 았는데 각 집의 피자배달거리는 해당 집과 도시의 존재 하는 피자집들과의 거리 중 최소값을 해당 집의 “피자배달거리”라고 한다. 집과 피자집의 피자배달거리는 |x1-x2|+|y1-y2| 이다. 예를 들어, 도시의 지도가 아래와 같다면

(1, 2)에 있는 집과 (2, 3)에 있는 피자집과의 피자 배달 거리는 |1-2| + |2-3| = 2가 된다. 최근 도시가 불경기에 접어들어 우후죽순 생겼던 피자집들이 파산하고 있습니다. 도시 시장은 도시에 있는 피자집 중 M개만 살리고 나머지는 보조금을 주고 폐업시키려고 합니다.
시장은 살리고자 하는 피자집 M개를 선택하는 기준으로 도시의 피자배달거리가 최소가 되는 M개의 피자집을 선택하려고 합니다.

도시의 피자 배달 거리는 각 집들의 피자 배달 거리를 합한 것을 말합니다.

▣ 입력설명
첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 12)이 주어진다. 둘째 줄부터 도시 정보가 입력된다.

 

▣ 출력설명
첫째 줄에 M개의 피자집이 선택되었을 때 도시의 최소 피자배달거리를 출력한다.

 

▣ 입력예제 1

4 4
0 1 2 0

1 0 2 1

0 2 1 2

2 0 1 2

 

▣ 출력예제 1

6

<풀이>

이 문제 같은 경우 나는 첫번째 방식의 효율이 너무 안좋아서 다시 풀었다. 첫번째 방식은 반복문 2번돌면서 DFS 호출하는식으로 했었는데 

시간이 너무 잡아먹힐꺼같아서 다른 방식으로 진행하다가 해당 예제에서 6개의 피자집중에서 2개를 버리고 4개를 선택하는거니까 조합으로 풀어야 되는 구나 라고 생각을 하게 되었다. (실제 강의도 풀이도 조합으로 푸는거 같다 조합을 앞전에 했었어서 비슷하게 생각할 수 있었던듯) DFS를 이용해서 피자집 개수 중에서 입력받은m개 피자집을 뽑는다(DFS에서 뽑기에 그만큼 level도 증가한다)

트리의 레벨이 입력받은 m값과 같으면 그만큼 피자집을 추려내서 선택했다는 거니까 앞 전에 집과 피자집을 각각의 리스트에 저장한 후 이중 for문을 통해서 하나의 집에서 모든 피자집의 거리를 계산해서 가장 작은 값만 변수(least_dis)에 저장한다 그 변수를 또다른 변수(com_dis)에 저장한다. 그렇게 해서 나온 도시의 피자 배달 거리를 비교해서 가장 작은 값을 출력한다.

 

<코드>

def DFS(x,l):
    global res_dis
    if l == m:
        # 4개를 뽑아서 올때마다 거리 비교
        com_dis = 0
        # print("뽑힌 피자집",C)
        # print("집 위치",H)
        for i in range(len(H)):
            least_dis = 99999999
            for j in range(len(C)):
                # print(abs(H[i][0]-C[j][0]) + abs(H[i][1] -C[j][1]))
                if least_dis > abs(H[i][0]-C[j][0]) + abs(H[i][1] -C[j][1]):
                    least_dis = abs(H[i][0]-C[j][0]) + abs(H[i][1] -C[j][1])
            # print("least_dis 값",least_dis)
            com_dis += least_dis   
        if res_dis > com_dis:
            res_dis = com_dis
            # print("res_dis값", res_dis)
    else:
        for i in range(x,len(P)): # 전체 피자집중에서 m개 뽑기
            C[l] = P[i] 
            DFS(i+1,l+1)
#### main
n , m = map(int,input().split())
L = [list(map(int,input().split())) for _ in range(n)]
P = [] # 피자 저장 리스트
H = [] # 집 저장 리스트
res_dis = 9999999
C=[0] * m # 피자집 중에서 m개 고르는 list 
for i in range(n):
    for j in range(n):
        if L[i][j] == 1:
            H.append((i,j))
        elif L[i][j] == 2:
            P.append((i,j))
DFS(0,0)
print(res_dis)

 

이 문제를 풀때 내가 엄청나게 실수한 부분이 있는데 least_dis 변수를 이중 for문 밖에 선언해서 least_dis가 하나의 집에서 모든 피자집의 거리를 확인해서 저장하고 넘기면 초기화를 시켰어야 했는데 이중 for문 밖에 넣으니까 그 다음값들이 초기화가 안됐다..(제일 작은 값만 계속 나왔다는 의미) print로 디버깅하는데 생각보다 많은 시간이 걸렸는데 실전에서 이러면 되게 멘붕올꺼같다... (조심하자 조심)