피자 배달 거리(삼성 SW역량평가 기출문제 : DFS활용)
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
DFS 두번 써서 시간초과 뜬 코드
import sys
sys.stdin = open("input.text", "rt")
sys.setrecursionlimit(10**6)
from collections import deque
n,m = map(int, input().split()) #m개의 피자집 선택시 도시의 최소 피자배달거리
g = [list(map(int, input().split())) for _ in range(n)]
pizza = []
home = []
for i in range(n):
for j in range(n):
if g[i][j] == 1: #집
home.append((i,j))
if g[i][j] == 2: #피자집
pizza.append((i,j))
#먼저 피자 m개 선택 후 그걸 다시 집에서 선택하도록 하다
r_p = [0] * m #m개 선택한거 저장하는 리스트
res = 24242424242424
def DFS(L,sum):
global res
if sum > res:
return
if L == len(home): #종료조건
if res > sum:
res = sum
else:
for i in range(len(r_p)):
temp = abs(home[L][0] - r_p[i][0]) + abs(home[L][1] - r_p[i][1])
DFS(L+1, sum + temp)
cnt = 0
def DFS_P(L,start):
global res
if L == m: #모두 선택, 종료조건
#피자집 4개 추출. 이제 홈에서 얘네를 선택. → 중복순열?
DFS(0, 0)
else:
for i in range(start, len(pizza)):
r_p[L] = pizza[i]
DFS_P(L+1, i+1) #현재꺼 선택
#리스트에 append, pop이 아니기에 백트랙킹 시 코드 필요없어. 알아서 되기 떄문
DFS_P(0,0)
print(res)
- m개의 피자집을 뽑고 다시 DFS로 거리를 구했다. 근데 사실 집, 피자집 모두 선택이 확정된 입장에서 DFS를 안돌리고 반복문으로도 해결이 가능했는데, 이걸 복잡하게 풀어버렸다.. (이걸 왜 생각 못했지 ?)
시간초과 해결 코드
import sys
# sys.stdin = open("input.text", "rt")
sys.setrecursionlimit(10**6)
from collections import deque
n,m = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]
#먼저 피자집에서 m개 선택
home = []
pizza = []
for i in range(n):
for j in range(n):
if g[i][j] == 1: #집
home.append((i,j))
if g[i][j] == 2: #피자집
pizza.append((i,j))
length = len(pizza)
select = [0] * m #선택된 피자
res = 24242424
def DFS(L,start):
global res
if L == m: #모두 선택. 종료조건
#m개 피자 선택했으니 도시의 최소 피자배달 거리 구해야함.
sum_dis = 0
for i in range(len(home)):
x1,y1 = home[i][0], home[i][1]
dis = 242424242
for j in select: #집마다 이제 m개의 피자집 중에 최소 피자배달거리 구해야함
x2 = pizza[j][0] #j에는 선택된 피자집의 인덱스가 있잖아!
y2 = pizza[j][1]
d = abs(x1-x2) + abs(y1-y2)
dis = min(d,dis)
#현재 집에서 최소 피자배달거리 dis로 구함.
sum_dis += dis #모든 집의 피자배달거리 더함.
res = min(res, sum_dis)
else:
for i in range(start, length):
select[L] = i #i번째 피자 선택.
DFS(L+1, i+1) #리스트 조회여서 백트랙킹 시 복구 코드 필요없음
DFS(0,0)
print(res)⚽ 코멘트
이 문제는 집, 피자집 총 2가지 조건이 존재했어 그렇기에 따로 집과 피자집 좌표를 저장해놨어야 했어. (문제에서 요구하는 순서대로 접근했어야 함)
그리고 먼저 M개를 선택하라고 했으니 피자집 중에 M개를 미리 선택해줘야 해(DFS-조합) (먼저 피자집을 선택해서 피자집에 대한 조건을 해결했어야 함)
- 이렇게 해당 개수를 뽑았다면 이제 다시 각 집에서 피자배달거리를 구해서 합이 최소거리를 얻어야 하는 문제였다.
for i in range(start, length):
select[L] = i #i번째 피자 선택.
DFS(L+1, i+1) #리스트 조회여서 백트랙킹 시 복구 코드 필요없음위 코드처럼 i번째 피자를 선택할 것이라면 다음 번에는 i+1부터 확인하도록 해야하니까 i+1을 줬어야함. (조합은 앞에서부터 뽑는 것으로 했으니)
- 처음 문제를 이해할 때는 어떻게 해야할지 감이 안왔다. (집, 피자집 거리를 어떻게 해야할까를 전혀 감을 못잡았기 때문..) 근데 피자집 m개를 미리 뽑으면 되지 않을까? 를 생각했고 그리고 다시 집과 m개의 피자집의 중복 순열의 경우의 수를 확인하면 됐다 !! (근데 나는 여기서 중복순열을 다시 DFS로 돌려서 시간초과를 만듬...)
- 그냥 반복문 돌려서 구하는게 가능했는데 이런거 생각잘하자.
- (i번째 집에서 선택된 모든 피자집 돌면서 최소거리 쉽게 구할 수 있었는데 복잡하게 이 거리도 DFS로 풀려고 했음)
⚽ 이번 삼성 코테 문제처럼 조합 + 다른 알고리즘 활용하는 문제가 자주 나온다고 한다. 그렇기에 확실하게 잘 준비해야 어떤걸 써야하는지를 알 것 같다. 공부 열심히 하자 !
