[Python] 백준 - 2618 경찰차

문제

어떤 도시의 중심가는 N개의 동서방향 도로와 N개의 남북방향 도로로 구성되어 있다.

모든 도로에는 도로 번호가 있으며 남북방향 도로는 왼쪽부터 1에서 시작하여 N까지 번호가 할당되어 있고 동서방향 도로는 위부터 1에서 시작하여 N까지 번호가 할당되어 있다. 또한 동서방향 도로 사이의 거리와 남 북방향 도로 사이의 거리는 모두 1이다. 동서방향 도로와 남북방향 도로가 교차하는 교차로의 위치는 두 도로의 번호의 쌍인 (동서방향 도로 번호, 남북방향 도로 번호)로 나타낸다. N이 6인 경우의 예를 들면 다음과 같다.

 

이 도시에는 두 대의 경찰차가 있으며 두 차를 경찰차1과 경찰차2로 부른다. 처음에는 항상 경찰차1은 (1, 1)의 위치에 있고 경찰차2는 (N, N)의 위치에 있다. 경찰 본부에서는 처리할 사건이 있으면 그 사건이 발생된 위치를 두 대의 경찰차 중 하나에 알려 주고, 연락 받은 경찰차는 그 위치로 가장 빠른 길을 통해 이동하여 사건을 처리한다. (하나의 사건은 한 대의 경찰차가 처리한다.) 그리고 사건을 처리 한 경찰차는 경찰 본부로부터 다음 연락이 올 때까지 처리한 사건이 발생한 위치에서 기다린다. 경찰 본부에서는 사건이 발생한 순서대로 두 대의 경찰차에 맡기려고 한다. 처리해야 될 사건들은 항상 교차로에서 발생하며 경찰 본부에서는 이러한 사건들을 나누어 두 대의 경찰차에 맡기되, 두 대의 경찰차들이 이동하는 거리의 합을 최소화 하도록 사건을 맡기려고 한다.

 

예를 들어 앞의 그림처럼 N=6인 경우, 처리해야 하는 사건들이 3개 있고 그 사건들이 발생된 위치 를 순서대로 (3, 5), (5, 5), (2, 3)이라고 하자. (3, 5)의 사건을 경찰차2에 맡기고 (5, 5)의 사건도 경찰차2에 맡기며, (2, 3)의 사건을 경찰차1에 맡기면 두 차가 이동한 거리의 합은 4 + 2 + 3 = 9가 되 고, 더 이상 줄일 수는 없다.

처리해야 할 사건들이 순서대로 주어질 때, 두 대의 경찰차가 이동하는 거리의 합을 최소화 하도록 사건들을 맡기는 프로그램을 작성하시오.

입력

첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1 ≤ W ≤ 1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄까지 사건이 발생된 위치가 한 줄에 하나씩 주어진다. 경찰차들은 이 사건들을 주어진 순서대로 처리해야 한다. 각 위치는 동서방향 도로 번호를 나타내는 정수와 남북방향 도로 번호를 나타내는 정수로 주어지며 두 정수 사이에는 빈칸이 하나 있다. 두 사건이 발생한 위치가 같을 수 있다.

출력

첫째 줄에 두 경찰차가 이동한 총 거리를 출력한다. 둘째 줄부터 시작하여 (i+1)번째 줄에 i(1 ≤ i ≤ W)번째 사건이 맡겨진 경찰차 번호 1 또는 2를 출력한다.

 

문제해결방법 - (구글링 참조)

 

1. 이 문제 많이 어렵다.. 변수 구성부터 함수 구성하는 것을 이해하는 것도 어려웠다.

 

2. 어떤 컨셉인가?

 

1) 일단 변수부터 구성하자.

 

- 경찰차의 위치 [1, 1], [n, n] 도 사건이라고 생각하자. 사건을 해결했다면 경찰차1이든, 경찰차2이든 그 사건 좌표에 위치하게 된다. 그러니 시작점도 사건리스트에 넣어준다고 생각하자.

 

 

d(사건리스트) = [[1, 1], [n, n]] + [list(map(int, input().split() for _ in range(w)] 

위 예제에서는 d = [[1, 1], [6, 6], [3, 5], [5, 5], [2, 3]] 이다.

 

 

d의 인덱스 0, 1, 2, 3, 4 중 0, 1은 이미 해결된 사건(혹은 경찰차1, 2의 시작점)이고, 그외 2, 3, 4는 앞으로 해결해야할 사건의 좌표이다. 

그리고 dp테이블과 path테이블을 구성한다. path리스트는 일단 나중에 보기로 한다. (역추적에 필요한 리스트기 때문. 일단은 사건해결의 최소값부터 생각하자.)

 

 

 

2) 핵심 로직을 생각해보자.

 

- 각 경찰차의 위치 또한 사건을 해결한 후의 위치라고 생각하기로 했다. 그렇다면 이런 패턴을 구해볼 수 있다.

 

가. 사건 2를 해결하는 최소값은? (d리스트의 인덱스 2번이 사건2다.)

 

 

dp[0][2] = min(   dist(경찰차1이 d[0]에서 사건2(d[2])로 이동한 값) +  sol(경찰차1이 d[2]에 있고, 경찰차2가 d[1]에 있을 때의 최소 이동거리),  dist(경찰차2가 d[1]에서 사건2(d[2])로 이동한 값) + sol(경찰차2가 d[2]에 있고, 경찰차1이 d[0]에 있을 때의 최소 이동거리) )

 

>> 괄호부분은 재귀함수(여기에서는 sol함수라 한다.)로 나뉘어져서 같은 로직으로 작동한다.

>> 이렇게 재귀함수(sol)로 타고 들어가다 사건이 5로 넘어가면 재귀함수는 0을 출력하게 만들고,  dist에서 구해진 거리값이 반영된다. 

 

나. 다음 사건은 어떻게 가리킬까?

 

next = max(경찰차1, 경찰차2)+1

 

경찰차1이든 경찰차2이든 가장 큰 사건의 인덱스보다 1이 더 큰 게 다음 사건이다.

 

결과적으로,

 

sol(0, 1)을 실행하면 sol(0, 2) + dist(1, 2) 혹은 sol(2, 1) + dist(0, 2) 중 최소값이 저장되는데, sol(0, 2)의 값이 결정되지 않았다.

> sol(0, 2)가 실행되고, 이 함수는 sol(0, 3) + dist(2, 3) 혹은 sol(3, 2) + dist(0, 3) 중 최소값이 저장되는데, 아직 sol(0, 3)이 결정되지 않았다.

 

> sol(0, 3)이 실행되고, 이 함수는 sol(0, 4) + dist(3, 4) 혹은 sol(4, 3) + dist(0, 4) 중 최소값이 저장되는데, 아직 sol(0, 4)이 결정되지 않았다.

 

>> sol(0, 4)의 next는 5이고, w+2와 같기 때문에, 0을 리턴한다.

 

>> 위 sol(0, 3)은 dist(3, 4) 와 dist(0, 4) 중 작은 값으로 결정되고, dp[0][3], path[0][3]에 반영되며, 타고타고 재귀함수가 리턴되어 각 dp[경찰차1][경찰차2]의 값들이 저장된다.

 

3) 최소값은 구했다. 각 사건을 어떤 경찰차가 해결했는지 어떻게 알지?

 

path에 1, 2로 구해놓았다. 

path[0][1]에는 다음 사건을 해결하는 경찰차가 1인지 2인지가 저장되어 있다.

 

만약 경찰차1이 사건2를 해결했다면, path[2][1]을 해결한 경찰차를 구하고, 

만약 경찰차2가 사건2를 해결했다면, path[0][2]를 해결한 경찰차를 구하면 된다. 

 

 

 

import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
w = int(input())
graph = [[1, 1], [n, n]]+[list(map(int, input().split())) for _ in range(w)]
dp = [[0 for _ in range(w+2)] for _ in range(w+2)]
path = [[0 for _ in range(w+2)] for _ in range(w+2)]

def dist(x, y):
	return abs(graph[x][0]-graph[y][0])+abs(graph[x][1]-graph[y][1])

def sol(c1, c2):
	if dp[c1][c2]:
		return dp[c1][c2]
	
	next = max(c1, c2)+1
	if next == w+2:
		return 0
	temp_A = sol(next, c2) + dist(c1, next)
	temp_B = sol(c1, next) + dist(c2, next)
	if temp_A < temp_B:
		dp[c1][c2], path[c1][c2] = temp_A, 1
	else:
		dp[c1][c2], path[c1][c2] = temp_B, 2
	return dp[c1][c2]

print(sol(0, 1))
c1, c2 = 0, 1
for i in range(2, w+2): # 2 3 4 
	print(path[c1][c2])
	if path[c1][c2] == 1:
		c1 = i
	else:
		c2 = i