[SWEA] 8382. 방향 전환 - Java

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

SW Expert Academy

---

1. 문제 요약

x1, y1에서 x2,y2로 가려고 한다.

이전에 가로로 이동했다면 이번엔 세로로 이동해야 하고,

이전에 세로로 이동했다면 이번엔 가로로 이동해야 한다.

이동횟수가 최소가 될 때의 이동 횟수가 답이 된다.

 

2. 풀이

수학, BFS 두 가지 방법으로 풀어보았다.

1) 수학

규칙으로 풀었다.

if (가로 차이) == (세로 차이) 라면,  ans = 가로 차이 + 세로 차이

if (가로 차이) > (세로 차이) 일 때,

        가로 차이가 짝수라면, ans = 가로차이 + 가로차이

        가로 차이가 홀수라면, ans = 가로차이 + (가로차이-1)

if (가로 차이) < (세로 차이) 일 때,  ans = 가로 차이 + 세로 차이

        세로 차이가 짝수라면, ans = 세로차이 + 세로차이

        세로 차이가 홀수라면, ans = 세로차이 + (세로차이-1)

if (가로 차이) == 0 라면,  ans = 가로 차이 + 세로 차이

if (세로 차이) == 0 라면,  ans = 가로 차이 + 세로 차이

 

 

2) BFS

 

 

3. 코드

수학

package a22_11_14;

import java.io.*;
import java.util.*;

public class SW_8382_방향전환 {

	static int sy, sx, ey, ex, ans;
	
	static int[] dy = {-1,1,0,0};
	static int[] dx = {0,0,-1,1};
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc<=T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			sy = Integer.parseInt(st.nextToken());
			sx = Integer.parseInt(st.nextToken());
			ey = Integer.parseInt(st.nextToken());
			ex = Integer.parseInt(st.nextToken());

			ans = 0;
			solution();
			System.out.println("#"+tc+" "+ans);
		}
	}
	
	static void solution() {
		int yGap = Math.abs(ey-sy);
		int xGap = Math.abs(ex-sx);
		if (yGap == 0) {
			for (int i=1; i<=xGap; i++) {
				if (i%2==0) ans+=3;
				else ans+=1;
			}
		} else if (xGap == 0) {
			for (int i=1; i<=yGap; i++) {
				if (i%2==0) ans+=3;
				else ans+=1;
			}
		} else {
			if (xGap > yGap) {
				if ((xGap+yGap) % 2 == 0) {
					ans = xGap+xGap;
				}
				else {
					ans = xGap+xGap-1;
				}
			} else if (xGap < yGap) {
				if ((xGap+yGap) % 2 == 0) {
					ans = yGap+yGap;
				}
				else {
					ans = yGap+yGap-1;
				}
			}else {
				ans = yGap+xGap;
			}
		}
	}
}

BFS

 

 

4. 사담