문제: https://www.acmicpc.net/problem/15686
BFS를 활용해서 풀이를 했다.
치킨집에 대한 배열을 만들고, 치킨집 하나하나를 bfs해가면서 각 집들과의 거리를 계산해주었다.
이때 각 집들과의 거리 합을 통해 합이 큰 순서대로 치킨집을 (전체치킨칩-m개) 만큼 삭제해주면 되겠다고 생각했다.
from collections import deque
n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(x, y):
q = deque()
q.append((x, y, 0))
visited = [[0]*n for _ in range(n)]
visited[x][y] = 1
chicken_len = []
while q:
if len(chicken_len) == len(house):
return chicken_len
x, y, count = q.popleft()
# print(x, y, count)
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<n and 0<=ny<n and not visited[nx][ny]:
if board[nx][ny] == 1:
chicken_len.append([count+1, (nx, ny)])
q.append((nx, ny, count+1))
visited[nx][ny] = 1
chicken = []
house = []
for x in range(n):
for y in range(n):
if board[x][y] == 1:
house.append((x, y))
elif board[x][y] == 2:
chicken.append((x, y))
chicken_lens = []
for i in range(len(chicken)):
chicken_len = bfs(chicken[i][0], chicken[i][1])
chicken_lens.append(chicken_len)
print(chicken_lens)
그렇게 코드를 짜고, 결과를 출력하면 다음과 같은 결과가 나온다
입력값
5 2
0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
2 0 0 1 1
2 2 0 1 2
출력값
[[[2, (1, 0)], [2, (1, 2)], [2, (0, 3)], [5, (3, 3)], [6, (4, 3)], [6, (3, 4)]],
[[2, (1, 0)], [3, (3, 3)], [4, (1, 2)], [4, (4, 3)], [4, (3, 4)], [6, (0, 3)]],
[[3, (1, 0)], [3, (4, 3)], [4, (3, 3)], [5, (1, 2)], [5, (3, 4)], [7, (0, 3)]],
[[2, (4, 3)], [3, (3, 3)], [4, (1, 0)], [4, (1, 2)], [4, (3, 4)], [6, (0, 3)]],
[[1, (3, 4)], [1, (4, 3)], [2, (3, 3)], [5, (0, 3)], [5, (1, 2)], [7, (1, 0)]]]
각 치킨집에서 출발했을 때, 집까지의 치킨거리들을 나타낸 것이다.
그런데 이중 m개의 치킨집만 남기는 조합을 생각해내기가 어려웠다.
조합으로 전체 경우의 수를 구해 풀 수 있긴하지만, 시간에 위배된다.
결국 답을 참고해서 문제를 풀었다.
치킨 거리를 구한 후 조합으로 풀려면, 조합의 경우가 너무 많이 생겨버린다.
따라서 처음부터 치킨집의 개수를 m개씩 묶어 조합을 생성하고, 각 조합별로 최단 거리를 구하면 된다.
(치킨집 개수는 최대 13개이기 때문에 시간복잡도를 통과한다.
from itertools import combinations
n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
chicken = []
house = []
for x in range(n):
for y in range(n):
if board[x][y] == 1:
house.append((x, y))
elif board[x][y] == 2:
chicken.append((x, y))
combi = list(combinations(chicken, m))
answer = 99999
for c in combi:
total = 0
for h in house:
temp = 9999
for i in range(m):
temp = min(temp, abs(h[0] - c[i][0]) + abs(h[1] - c[i][1]))
total += temp
answer = min(answer, total)
print(answer)
조합으로 풀긴했지만, 백트래킹 완전탐색으로도 풀 수 있는지 오후에 찾아봐야겠다!
'코딩테스트' 카테고리의 다른 글
[Python] 백준 14891번 - 톱니바퀴 (0) | 2023.08.01 |
---|---|
[Python] 백준 15686번 - 치킨 배달 (dfs 백트래킹) (0) | 2023.07.18 |
[Python] 백준 21608번 - 상어 초등학교 (0) | 2023.07.13 |
[Python] 백준 14502번 - 연구소 (0) | 2023.07.12 |
[Python] 백준 18870번 - 좌표 압축 (0) | 2023.07.11 |