[삼성 SDS 알고리즘 사전테스트] 순환공간

[삼성 SDS 알고리즘] 순환공간

지난 일요일 사전테스트가 종료되었습니다. 테스트기간동안 푼 문제 해결방법을 포스팅하려고 합니다.

문제 출처 : https://koitp.org/problem/SDS_TEST_PAGE/read/

문제

N 개의 행, M 개의 열로 이루어진 직사각형 모양의 말판이 있다. 이 말판의 각 칸은 정사각형으로 이루어져 있으며, 당신의 말은 이 말판의 칸 중 한 곳(출발지)에 위치해 있다고 한다.

당신의 말은 상, 하, 좌, 우 방향의 인접한 곳으로 한 번에 한 칸씩 이동할 수 있으며, 특정 목적지까지 최소의 이동횟수로 가는 방법을 찾고자 한다.

그런데 이 말판은 특이한 특징이 있는데, 가장 왼쪽 칸에서 왼쪽으로 한 칸 이동하면 그 행의 가장 오른쪽 칸으로 가며, 마찬가지로 가장 오른쪽 칸에서 오른쪽으로 한 칸 이동하면 그 행의 가장 왼쪽 칸으로 가게 된다. 이러한 특징은 위, 아래 방향으로도 마찬가지이다. 즉 가장 위쪽 칸에서 위로 한 칸 이동하면 그 열의 가장 아래쪽 칸으로 가며, 가장 아래쪽 칸에서 아래로 한 칸 이동하면 그 행의 가장 위쪽 칸으로 가게 된다.

이 말판의 칸의 위치를 편의상 (행, 열) 좌표로 표시하기로 할 때 출발지를 (r1, c1), 목적지를 (r2, c2) 라고 가정하자.

이 경우 당신의 말이 출발지 (r1, c1) 에서 목적지 (r2, c2) 까지 이동할 때의 최소 이동횟수가 몇 회인지를 알아내는 프로그램을 작성하여라.

본 문제에서 모든 좌표는 0부터 시작함에 유의하자.

[제한조건]

1. N, M 은 각각 1 이상 1000000(백만) 이하의 정수이다.
2. r1, r2 는 각각 0 이상 N-1 이하의 정수이다.
3. c1, c2 는 각각 0 이상 M-1 이하의 정수이다.

입력

첫 줄에 테스트 케이스의 개수 T(<=25)가 주어지며, 그 다음 줄부터 T 개의 테스트 케이스가 차례로 주어진다.

각 테스트케이스는 한 줄로 구성되어 있으며, N, M, r1, c1, r2, c2 가 공백으로 구분되어 차례로 주어진다.

출력

각각의 테스트 케이스에 대하여 #x (x는 테스트 케이스 번호, 1부터 시작) 을 출력하고 공백을 하나 둔 다음, (r1, c1) 으로부터 (r2, c2) 까지 이동할 때의 최소 이동횟수를 출력한다.

힌트

(입력)
3
3 3 0 0 2 2
4 6 3 4 2 0
394 549 254 477 15 414

(출력)
#1 2
#2 3
#3 218

계획 및 분석

N*M 크기의 말판에서 출발지(r1, c1)와 도착지(r2, c2)를 입력하고 최소 이동횟수를 구하는 문제입니다. 얼핏보면 간단해보이는 문제지만, 까다로운 조건이 존재합니다. 바깥쪽을 통해서 정반대 말판으로 이동할 수 있는 조건인데요. 이 때문에 그냥 말판 안에서 최소 이동횟수만으로는 답을 구할 수 없게 됩니다. 

처음에는 말판에 대한 2차원 배열을 생성하려고 했는데, 행과 열에 해당하는 N과 M이 최대 100만까지 가능한 큰 수 였기 때문에 불가능했습니다. 이 때문에 어떤 방식으로 문제를 풀어야할 지 생각하는 시간이 상당히 오래걸렸습니다ㅠㅠ 하지만 이 문제는 배열을 생성하지 않아도 해결이 가능했습니다.

출발지와 도착지가 바깥쪽을 이용해 가는 것이 이동거리가 짧은 규칙을 찾아야 합니다. 바깥쪽을 이용하지 않는다면, 출발지(r1, c1)와 도착지(r2, c2)라고 가정했을 때 최소 이동거리는 (r1-r2)의 절대값 + (c1-c2)의 절대값입니다.

바깥쪽을 이용하게 된다면, 말판의 행과 열을 출발지와 도착지 중 더 큰 수와 빼고 작은 수와 더한 합이 이동거리가 됩니다. (직접 손으로 규칙을 찾아보니 이런 연산식으로 나타낼 수 있었습니다.)

만약 바깥쪽을 이용한 이동거리 크기가 더 작으면, 이게 정답이 되겠죠?

N행에 해당하는 r1과 r2의 이동거리는 sum1로 저장하고, M열에 해당하는 c1과 c2의 이동거리는 sum2로 저장했습니다.

각각 큰 값과 작은 값을 저장할 변수도 만들어줬고, 조건에 맞게 저장시켜 활용했습니다.

            int sum1 = r1 - r2;
            int sum2 = c1 - c2;
            if (sum1 < 0) // 음수가 나오면 양수로
                sum1 = -sum1;
            if (sum2 < 0)
                sum2 = -sum2;
 
            int bigr, smallr, bigc, smallc; //큰 값, 작은 값을 저장할 변수 선언
            if (r1 > r2) {
                bigr = r1;
                smallr = r2;
            }
            else {
                bigr = r2;
                smallr = r1;
            }
            if (c1 > c2) {
                bigc = c1;
                smallc = c2;
            }
            else {
                bigc = c2;
                smallc = c1;
            }
 
 
            if (sum1 >= ((N + smallr) - bigr)) // 그냥 두 좌표의 거리보다 바깥쪽으로 가는게 이동횟수 빠를 때
                sum1 = ((N + smallr) - bigr);
            if (sum2 >= ((M + smallc) - bigc))
                sum2 = ((M + smallc) - bigc);
 
 
            count[i] = sum1 + sum2; // 두 거리 합 저장

바깥쪽으로 가는게 더 빠른지 조건을 걸어 최소 이동거리를 count 변수에 저장시키며 해결할 수 있었습니다.

꼭 2차원 배열을 이용하지 않아도 규칙을 찾아 답을 구할 수 있다는 걸 깨달은 문제였습니다. 실제로 문제를 풀 때 무작정 풀려고 하지 않고 접근방향에 대해서 차근차근 생각해 진행함이 중요할 것 같습니다. 

전체 소스 코드

#include <iostream>
 
using namespace std;
 
int main() {
    int T, N, M, r1, c1, r2, c2;
 
    cin >> T; //testcase
 
    int count[25] = { 0, };
 
    for (int i = 0; i < T; i++) {
        cin >> N >> M >> r1 >> c1 >> r2 >> c2;
 
        if (r1 <= (N - 1) && r2 <= (N - 1) && c1 <= (M - 1) && c2 <= (M - 1)) {
             
            int sum1 = r1 - r2;
            int sum2 = c1 - c2;
            if (sum1 < 0) // 음수가 나오면 양수로
                sum1 = -sum1;
            if (sum2 < 0)
                sum2 = -sum2;
 
            int bigr, smallr, bigc, smallc; //큰 값, 작은 값을 저장할 변수 선언
            if (r1 > r2) {
                bigr = r1;
                smallr = r2;
            }
            else {
                bigr = r2;
                smallr = r1;
            }
            if (c1 > c2) {
                bigc = c1;
                smallc = c2;
            }
            else {
                bigc = c2;
                smallc = c1;
            }
 
 
            if (sum1 >= ((N + smallr) - bigr)) // 그냥 두 좌표의 거리보다 바깥쪽으로 가는게 이동횟수 빠를 때
                sum1 = ((N + smallr) - bigr);
            if (sum2 >= ((M + smallc) - bigc))
                sum2 = ((M + smallc) - bigc);
 
 
            count[i] = sum1 + sum2; // 두 거리 합 저장
 
        }
    }
 
    for (int i = 0; i < T; i++) {
        cout << "#" << i + 1 << " " << count[i] << endl;
    }
}