[SWEA] D4 3349 최솟값으로 이동하기

문제 출처

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWDTN0cKr1oDFAWD

문제

한국의 모든 구획이 새롭게 재편성되었다.

정확히 말하면 W개의 남북방향 도로와 H개의 동서방향 도로가 모두 일정한 간격으로 늘어서서 교차하는 바둑판 모양으로 만들었다.

남북방향 도로는 가장 서쪽에 있는 것으로부터 시작해서 동쪽으로 가면서 차례대로 1, 2, …, W로 번호가 매겨져 있고,

동서방향 도로는 가장 남쪽에 있는 것으로부터 시작해서 북쪽으로 가면서 차례대로 1, 2, …, H로 번호가 매겨져 있다.

i번 남북방향 도로와 j번 동서방향 도로가 교차하는 지점을 (i, j)로 나타낸다.

이렇게 도로를 만들고 나면 아래와 같은 모양이 된다.

W = 4, H = 3인 예이다.

 

정부는 이런 식으로 도로를 만들면 중간에 사용하지 않는 공간이 너무 많은 것 같아서 북동방향으로 가는 도로도 만들었다.

즉 (i, j)와 (i - 1, j - 1)을 연결하는 도로이다.

이런 도로를 만든 다음에는 아래와 같아질 것이다.

 

 

준환이는 최근에 일이 많아서 N개의 교차로를 순서대로 이동해야 한다. 

i번째로 이동하려는 지점은 (xi, yi)이다.

정부에서는 교차로에서 다른 교차로로 한번 이동할 때 1만큼의 비용을 내도록 정책을 세웠기 때문에 비용을 줄이기 위해 적절한 전략을 세워야 한다.

준환이는 (x1, y1)에서 시작하여 i가 증가하는 순서대로 (xi, yi)들을 차례대로 방문하고 (xN, yN)에 도착하기 위해 드는 비용의 최솟값이 무엇인지 궁금하다.

이를 구하는 프로그램을 작성하라.


[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 세 정수 W, H, N(2 ≤ W, H ≤ 10,000, 1 ≤ N ≤ 1,000)이 공백으로 구분되어 주어진다.

다음 N개의 줄의 i번째 줄에는 두 정수 xi, yi (1 ≤ xi ≤ W, 1≤ yi ≤ H)가 공백으로 구분되어 주어진다.


[출력]

각 테스트 케이스마다 x1, y1 에서 시작하여 i가 증가하는 순서대로 (xi, yi) 들을 차례대로 방문하고 (xN, yN)에 도착하기 위해 드는 비용의 최솟값을 출력한다.

 

1 4 3 3 1 1 3 3 4 1

#1 5

풀이

최단거리를 구하는 문제라 바로 BFS를 떠올리고 BFS로 문제를 풀었지만 시간초과가 났다.

다른 방법을 찾으려고 하였고 규칙을 발견하여 문제를 풀게 되었다. 

대각선을 이용할 수 있는 경우와 없는 경우로 나눠서 생각하면 된다. 대각선을 이용할 수 없는 경우에는 그냥 가로와 세로 거리를 구하면 되며 대각선 이용이 가능한 경우에는 대각선 횟수를 구한 후 나머지 세로 가로 거리를 구하면 된다.

아래 그림을 보면 현재 위치가 (3,2) 로 가정했을 때 현위치의 x,y가 목적지의 x,y와 비교했을 때 하나는 크고 하나는 작다면 대각선 이용이 불가하다. 아래 그림을 보게 되면 파란색 체크한 부분의 경우이다.

• (2,3)의 경우 현 위치의 x가 크고 y가 작다
• (4,1)의 경우 현 위치의 x가 작고 y가 크다

 

코드

T = int(input())
for t in range(T):
    W, H, N = map(int,input().split())
    way = [list(map(int,input().split())) for _ in range(N)]
    X, Y = way[0][0], way[0][1]
    result = 0
    for x,y in way:
        if (X > x and Y < y) or (X < x and Y > y): # x나 y값 둘 중 하나만 크면 대각선 이용 불가
            result += (abs(X-x) + abs(Y-y)) 
        else: # min(abs(X-x),abs(Y-y))만큼 대각선 사용 + 나머지 가로,세로방향거리
            result += (min(abs(X-x),abs(Y-y)) + abs(abs(X-x)-abs(Y-y)))
        X,Y = x,y # 현 위치 변경
    print('#{} {}'.format(t+1,result))

 

회고

처음 BFS로 풀때 테스트케이스의 데이터 자체가 가로 세로 10000개씩이라 시간초과가 나는 것 같다. BFS로 풀기 전에 시간복잡도를 계산하고 풀 수 있는지 검토하는 과정을 가졌어야 했는데 아직까지는 시간복잡도 구하는 것 자체가 어려워 그러지 못했다. 이제부터는 시간복잡도 계산도 해보는 시간을 가지면서 시간복잡도와 친해지는 시간을 가져야할 것 같다. 

또 이번에도 문제를 정말 잘 읽어야 한다는 것을 다시 한번 느꼈다. 무조건 1,1에서 시작인줄 알았는데 그게 아니라 x1,y1에서 시작이었다... 이것 때문에 정말 1시간 넘게 삽질했다... 문제 정말 잘 읽자...