[SWEA] 8382.방향 전환 (java) / 시뮬레이션

@시뮬레이션 / 25m

처음에는 완탐인가? 아님 다른건가? 하면서 되게 쫄았는데

오히려 쉽게 생각하니 바로 풀렸다.

요새 자꾸 너무 어려운것만 풀어서 계속 어렵게 생각하는 경향이 있는 것 같다.

골고루 풀어야 할 듯!

 

 

문제 링크

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

SW Expert Academy

 

 

사고 흐름

1. 문제를 처음 봤을 때는, 이거 그냥

Math.abs(x1 - x2) + Math.abs(y1 - y2) 이러면 되는거 아닌가..? 했는데

무조건 이전에 이동한 방향과 다른 방향으로 이동해야 하므로, 이렇게 풀면 망한다 ㅎㅎ

 

 

2. 다음으로 한 생각은, 완탐을 돌려서, 이전 턴에 가로를 뽑았으면 이번 턴에는 세로만 뽑는 식으로 풀어볼까 했다.

그런데 이렇게 돌리면 맵 사이즈가 201 * 201인데 터질 것 같아서 접었다.

 

 

3. 그럼 도대체 어떻게 풀지..? 하다가

사람의 사고방식으로는 3번 테케를 어떻게 풀지? 생각해봤다.

0 0 0 2 에서

원래는 가로 이동을 두 번만 하면 도착 할 수 있지만, 이 문제에서는 가로-세로-가로-세로 이렇게 이동해야 한다.

만약 원래는 안 해도 될 이동을 해야 한다면, 최대한 도착점과 멀어지지 않게끔 이동해야 된다 라고 생각했다.

이 방법으로 풀었다.

 

 

풀이 방법

1. 완탐이 아니기 때문에, 도착점을 찾을 때까지 무한루프를 돌았다.

 

 

2. 일단 이동한 방향을 boolean형 변수에 저장했다.

지금 턴에 가로로 이동했다면 flag = true, 세로로 이동했다면 flag = false로.

 

 

3, flag에 따라서 이전 턴의 이동 방향과 반대로 이동한다.

이때 만약 가로로 이동한다면, 도착점이 지금점보다 왼쪽에 있다면 왼쪽으로 이동하고,

오른쪽에 있다면 오른쪽으로 이동하게 한다.

 

 

4. 가장 중요한건 함수를 두번 불러줘야 한다.

이전 이동방향이 가로일때, 세로일때 한번씩 총 두번!

+ 시간을 좀 줄여보려고, 한번에 최솟값(x좌표 차이 + y좌표차이)을 찾은 경우, 끝내도록 짜 봤지만

오히려 더 오래 걸려서, 원래 코드가 더 나은 것 같다.

 

 

소스 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
     
    private static int x1, x2, y1, y2, min;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
         
        int T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            min = Integer.MAX_VALUE;
 
            st = new StringTokenizer(br.readLine());
            x1 = Integer.parseInt(st.nextToken());
            y1 = Integer.parseInt(st.nextToken());
            x2 = Integer.parseInt(st.nextToken());
            y2 = Integer.parseInt(st.nextToken());
             
            move(true);
            move(false);
            sb.append("#" + t + " " + min + "\n");
        }
        System.out.println(sb);
    }
 
    private static void move(boolean flag) {
        int dx = x1, dy = y1, count = 0;
         
        while (true) {
            if (dx == x2 && dy == y2) {
                if (min > count) min = count;
                break;
            }
             
            if (flag) {
                if (dy > y2) dy--;
                else dy++;
                flag = false;
                 
            } else {
                if (dx > x2) dx--;
                else dx++;
                flag = true;
            }
            count++;
        }
    }
}

 

무난했다.

 

끝!