[Platinum IV] 경찰차 - 2618

문제 링크

성능 요약

메모리: 70328 KB, 시간: 4316 ms

분류

다이나믹 프로그래밍

문제 설명

어떤 도시의 중심가는 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), (N, N)에서 시작한다.
• 첫째줄에 N이 주어지고, 둘째줄에 처리할 사건의 개수 m, 그 이후로 m줄동안 처리할 사건이 발생한 지점의 좌표가 주어진다.
• 두대의 경찰차들이 이동하는 거리의 합을 최소화 하도록 하여, 경찰차가 이동한 거리, 각 사건마다 배정된 경찰차의 번호를 출력한다.

우선 2차원 좌표에서 사건을 처리하는 방법을 구하기는 조금 까다로울것이라 판단하여, 약간 문제를 변형하여 아이디어를 먼저 얻어보기로 했다.

좌표를 1차원으로 변형하고 총 이동 거리를 구한다면 기존의 최적화 문제를 푸는 방식대로 문제를 풀이할 수 있을것이라고 판단하였다.

♻ 문제 변형하기

$0$ 부터 $N$까지 있는 리스트에, 경찰차 두대가 각각 $0$번과 $N$번에 위치한다고 하자.
사건이 발생한다고 할때 최소 이동 거리와, 각 사건마다 해결한 경찰차의 번호를 출력한다.

♻ 변형 문제 풀이

테스트 케이스를 하나 임시로 만들었다.

6
3
3
5
1

이때 그림으로 표현하면 2가지의 부분문제로 바라볼 수 있다.

• A 경찰차가 이동하는 경우 : 거리(3)
• B 경찰차가 이동하는 경우 : 거리(2)
  

이를 기반으로 함수의 입력값과 반환값을 설정하면
solve(A위치, B위치, 목표 위치) => 이동거리의 최솟값
이 함수를 구현해보자.

INF = 1001
posA, posB = 0, int(input())
e = int(input())
events = list(map(lambda x:x-1, [int(input()) for _ in range(e)]))

def get_dist(p1, p2):
    return abs(p1-p2)

def solve(pa, pb, pe):
    if pa >= pb:    # 경찰차 A가 B를 타고 넘는 경우
        # print(pa, pb, INF)
        return INF
    
    if pe == e:     # 이벤트의 끝에 도달한 경우
        # print(pa, pb, "end")
        return 0
    
    # print(pa, pb, pe)
    if dp[pa][pb] != -1:
        return dp[pa][pb]
    
    dp[pa][pb] = min(solve(events[pe], pb, pe+1) + get_dist(pa, events[pe]),
               solve(pa,events[pe], pe+1) + get_dist(pb,events[pe]))
    
    return dp[pa][pb]


print(solve(posA, posB-1, 0))

함수와 변수의 역할에대해 간략하게 설명하자면

• get_dist : 목표지점과 움직일 경찰차 사이의 거리를 구한다
• solve : 두 경찰차의 위치와, 사건이 발생한 위치를 입력받아 움직이는 경찰차의 최소 거리를 반환한다.
• pa, pb, e: 각각 경찰차A, 경찰차B, 사건이 발생한 좌표이다.
• res : 부분 문제에서의 최소거리이다. 해당 부분문제에서의 최소값에 다음 부분문제에서의 최소값을 누적한다.

점화식은 아래와 같다.

여기서 이벤트별로 처리하는 경찰차가 무엇인지 역추적해야 한다.
그러나 베낭문제 역추적과 마찬가지로 경우의 수가 2개밖에 없으므로 재구성하기위한 별도의 공간은 필요해보이지 않는다.

# 전처리 생략
# 재구성 부분만 첨부

picked = []
def reconstruct(pa, pb, pe):
    if pe == e: # 이벤트의 끝에 도달했을때 return
        return 
    
    if solve(pa, pb, pe) == solve(events[pe], pb, pe+1) + get_dist(pa, events[pe]):
        picked.append("A")
        reconstruct(events[pe], pb, pe+1)

    else:
        picked.append("B")
        reconstruct(pa, events[pe], pe+1)

이제 2차원으로 넘어갈 차례이다.

💥 원래 문제 풀이 (시도1)

구성하는 문제의 좌표가 2차원이 되면 바뀌는 것이 무엇인가 생각해보자.

• 좌표값이 2차원이 되므로, 거리를 계산하는 함수 get_dist의 계산 방식이 달라질 것이다.
• 조건1인 A가 B를 넘어서는 경우를 판별하는 방법이 달라질것이다. 조금 더 정확히 설명하자면 무조건 B가 가야하는 경우, 또는 무조건 A가 가야 최적인 경우이다.
• 이벤트의 끝에 도달하는 경우가 2차원 좌표값을 갖는다.
• 기저사례의 경우 reconstruct의 경우에도 동일하다.

기저사례를 먼저 해결해보자.

• 사건이 끝난경우 종료
• A가 B를 넘어간 경우의 판단은 A의 현재위치와 B의 현재위치에서 수직으로 내렸을 때 서로 같은 거리를 가지게 하는 직선을 기점으로 판단하면 된다라고 생각하는데 우선 구현하지 않고 전부 탐색하는 방법으로 해보고 시간 이슈가 있으면 구현.

---

1. 사건을 입력받는 부분을 수정하였다.

events = [list(map(lambda x:x-1, list(map(int, input().split())))) for _ in range(e)]

2. 거리를 계산하는 코드는 x좌표 y좌표 변화량의 합이므로 아래와같이 수정하였다.

def get_dist(p1, p2):
    return abs(p1[0]-p2[0]) + abs(p1[1] - p2[1])

3. 일단 DP를 제거하고 완전탐색으로 solve를 구현한다

def solve(pa, pb, pe):
    if pe == e:     # 이벤트의 끝에 도달한 경우
        # print(pa, pb, "end")
        return 0
    
    # print(pa, pb, pe)
    res = min(solve(events[pe], pb, pe+1) + get_dist(pa, events[pe]),
               solve(pa,events[pe], pe+1) + get_dist(pb,events[pe]))
    
    return res

4. 함수 Solve와 Recoustruct의 입력값을 2차원에 맞게 수정한다.

reconstruct(posA, list(map(lambda x:x-1, posB)), 0)
print(picked)
    

print(solve(posA, list(map(lambda x:x-1, posB)), 0))

5. DP를 적용하고, 문제 출력에 맞게 출력형식을 재구성한다.

1. DP 적용전 완성 코드

INF = 1001
posA, posB = [0, 0], [k:=int(input()), k]
e = int(input())
events = [list(map(lambda x:x-1, list(map(int, input().split())))) for _ in range(e)]

def get_dist(p1, p2):
    return abs(p1[0]-p2[0]) + abs(p1[1] - p2[1])

def solve(pa, pb, pe):
    if pe == e:     # 이벤트의 끝에 도달한 경우
        # print(pa, pb, "end")
        return 0
    
    # print(pa, pb, pe)
    res = min(solve(events[pe], pb, pe+1) + get_dist(pa, events[pe]),
               solve(pa,events[pe], pe+1) + get_dist(pb,events[pe]))
    
    return res

picked = []
def reconstruct(pa, pb, pe):
    if pe == e: # 이벤트의 끝에 도달했을때 return
        return 
    
    if solve(pa, pb, pe) == solve(events[pe], pb, pe+1) + get_dist(pa, events[pe]):
        picked.append("1")
        reconstruct(events[pe], pb, pe+1)

    else:
        picked.append("2")
        reconstruct(pa, events[pe], pe+1)



print(solve(posA, list(map(lambda x:x-1, posB)), 0))
reconstruct(posA, list(map(lambda x:x-1, posB)), 0)
for i in picked:
    print(i)

# print_dp()

💥 원래 문제 풀이 (시도2)

2차원 DP로 한정지어 아무리 생각해봐도 3차원 DP말고는 답이 없을것 같다는 생각이 들었다.
그래서 질문게시판에 올려봤는데 새로운 아이디어를 제시해주셨다..!

이를 기반으로 다시 한 번 생각해본다.

코드

import sys
sys.setrecursionlimit(int(1e8))
MAX = 1001
INF = 1e9+7
dp = [[-1]* MAX for _ in range(MAX)]
trace = []
def get_dist(a, b):
    # print(a, b)
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def solve(posA, posB):

    if posA == m or posB == m:
        return 0
    
    if dp[posA][posB] != -1:
        return dp[posA][posB]
    
    nxt = max(posA, posB)+1
    # print(posA, posB, nxt)
    if not posA:
        dp[posA][posB] = solve(nxt, posB) + get_dist([1,1], events[nxt])
    else:
        dp[posA][posB] = solve(nxt, posB) + get_dist(events[posA], events[nxt])
    
    if not posB:
        dp[posA][posB] = min(solve(posA, nxt) + get_dist([n, n], events[nxt]), dp[posA][posB])
    else:
        dp[posA][posB] = min(solve(posA, nxt) + get_dist(events[posB], events[nxt]), dp[posA][posB])

    return dp[posA][posB]

def reconstruct(posA, posB):
    if posA == m or posB == m:
        return
    
    nxt = max(posA, posB)+1   
    
    if not posA:
        a = solve(nxt, posB) + get_dist([1, 1], events[nxt])
    else:
        a = solve(nxt, posB) + get_dist(events[posA], events[nxt])
    
    if not posB:
        b = solve(posA, nxt) + get_dist([n, n], events[nxt])
    else:
        b = solve(posA, nxt) + get_dist(events[posB], events[nxt])
    
    if a > b:
        trace.append(2)
        reconstruct(posA, nxt)
    else:
        trace.append(1)
        reconstruct(nxt, posB)


n = int(input())
m = int(input())
events = [[]]*(m+1)
for i in range(1, m+1):
    events[i] = list(map(int, input().split()))

print(solve(0, 0))
reconstruct(0, 0)
for i in trace:
    print(i)

dp에 대한 아이디어를 도움받고 약간의 참고를 하여 코드를 완성시켰다.

---

회고

처음 시작할때만해도 완벽하게 풀이한 줄 알았고 설렜었는데, 조금 아쉬웠다. 하지만 실력이 늘었다는것을 반증했고 다양한 도움들 끝에 탑다운으로 코드를 완성시킨것이 좋았던 점이다.