[SWEA] 8382. 방향 전환

[SWEA] 8382. 방향 전환

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWyNQrCahHcDFAVP&categoryId=AWyNQrCahHcDFAVP&categoryType=CODE&problemTitle=8382&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

 

방법 1> BFS

1. 가로→ 세로, 세로→ 가로로만 이동 가능
   • 첫 이동은 어떤 이동이든 상관x (cf) 파이프 문제는 가로로 시작
2. visited 배열 3차원으로 사용하기
   • 한 위치 (x1, y1)는 가로로 들어왔을 때, 세로로 들어왔을 때를 구분한다 → 3차원 배열 사용
3. 음수 좌표 존재 → 양수화하여 사용
   • x1, y1, x2, y2 (-100 ≤ x1, y1, x2, y2 ≤ 100)
     • 입력 x1, y1, x2, y2 가 음수일 수 있다.
     • 범위 양수화 → 0 ~ 200

import java.io.*;
import java.util.*;
// 210322

public class Solution_D4_8382_방향전환_2 {
	static int min;
	static int x1, y1, x2, y2;

	static int stoi(String str) {
		return Integer.parseInt(str);
	}

	static class Data {
		int x, y;
		int cnt; // 몇번만에 움직였는지
		int dir;
		
		public Data(int x, int y, int cnt, int dir) {
			super();
			this.x = x;
			this.y = y;
			this.cnt = cnt;
			this.dir = dir;
		}	
	}
	
	// dfs(x, y, cnt, dir) -> dfs는 보통 parameter로 들고 다님
	static int[] dx = {0, 0, -1, 1}; // 상하 좌우
	static int[] dy = {-1, 1, 0, 0}; // 세로 가로
	
	static void bfs() {
		Queue<Data> q = new ArrayDeque<>();
		boolean[][][] v = new boolean[201][201][2]; // -100 ~ 100, (0,0)도 포함
													// 3차원 방문 체크, 0 가로, 1 세로
		
		q.offer(new Data(x1, y1, 0, 0)); // 시작점, 맨 처음은 0으로 센다, dir = 0 가로, 1 세로
		v[y1][x1][0] = true; // y가 세로 방향인거 주의하기
		q.offer(new Data(x1, y1, 0, 1)); // dir = 0 가로, 1 세로 -> 첫 이동은 어떤 이동이든 상관x (가로, 세로 둘 다 시
		v[y1][x1][1] = true;
		
		Data cur = null;
		int nx, ny;
		while(!q.isEmpty()) {
			cur = q.poll(); // x2, y2에 도착해야 함
			if(cur.x == x2 && cur.y == y2) { // 나중에 와도 이거보다 최단 거리일 수 x
				min = cur.cnt; // 현재 몇번만에 왔는지
				return;
			}
			
			// 가로 -> 세로
			if(cur.dir == 0) {
				for(int d=0; d<2; d++) {
					nx = cur.x + dx[d];
					ny = cur.y + dy[d];
					// 범위 체크
					if(nx<0 || nx>=201 || ny<0 || ny>=201) continue;
					// 방문 체크
					if(v[ny][nx][1]) continue;
					// 재방문 위해 큐에 삽입
					q.offer(new Data(nx, ny, cur.cnt+1, 1));
					v[ny][nx][1] = true;
				}
			}
			
			// 세로 -> 가로
			if(cur.dir == 1) {
				for(int d=2; d<4; d++) {
					nx = cur.x + dx[d];
					ny = cur.y + dy[d];
					// 범위 체크
					if(nx<0 || nx>=201 || ny<0 || ny>=201) continue;
					// 방문 체크
					if(v[ny][nx][0]) continue;
					// 재방문 위해 큐에 삽입
					q.offer(new Data(nx, ny, cur.cnt+1, 0));
					v[ny][nx][0] = true;
				}
			}
		}
		
	}
	
	public static void main(String[] args) throws Exception {
		//System.setIn(new FileInputStream("res/input_D4_8382_방향전환.txt"));/
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		int T = stoi(br.readLine());
		for(int tc=1; tc<=T; tc++) {
			
			st = new StringTokenizer(br.readLine().trim(), " ");
			min = Integer.MAX_VALUE;
			
			x1= stoi(st.nextToken()) + 100;  // 음수 -> 양수화
			y1 = stoi(st.nextToken()) + 100; 
			x2 = stoi(st.nextToken()) + 100; 
			y2 = stoi(st.nextToken())+ 100; 
			
			bfs();
			
			sb.append("#" + tc + " " + min + "\n");
		}
		System.out.println(sb.toString());
		
		br.close();
	} //
}

 

 

---

방법 2> 좌표값 계산

 

1. 좌표 위치가 endX, endY를 넘어가도 괜찮다. 

(0, 0) -> (0, 2)의 경우 오른쪽으로 두 번 갈 수 없기 때문에 가로 세로를 번갈아 가야한다.

(0, 0) -> (1, 0) -> (1, -1) -> (2, -1) -> (2, 2) (cnt=4) 

 

2.  가로 / 세로 방향은 flag로 정해지며, 

가로로 가야할 때 목표 위치의 x값이 현재 위치 x값보다 크면 오른쪽으로만. 작거나 같으면 왼쪽으로만 가면 된다.

(우로 갔다가 다시 좌로 돌아오는 등의 과정을 거치면 최소값이 나오지 않는다.)

세로 방향도 마찬가지다.

import java.io.*;
import java.util.*;
// 210315

public class Solution_D4_8382_방향전환 {
	static int min;
	static int[] start, end;
	static int startX, startY, endX, endY;

	static int stoi(String str) {
		return Integer.parseInt(str);
	}
	
	static void go(int x, int y, boolean flag, int cnt) { // flag=true 가로, flag=false 세로
		
		if(x==endX&&y==endY) {
			min = Math.min(min, cnt);
			return;
		}
		
		if(flag) { // 가로로 가라
			if(x < endX) { // 우 방향
				go(x+1, y, false, cnt+1); // 다음 방향은 세로
			} else { // 좌 방향
				go(x-1, y, false, cnt+1); // 다음 방향은 세로
			}
		} else { // 세로로 가라
			if(y < endY) {
				go(x, y+1, true, cnt+1); // 위로
			} else {
				go(x, y-1, true, cnt+1); // 아래로
			}
		}
		
	}

	public static void main(String[] args) throws Exception {
		//System.setIn(new FileInputStream("res/input_D4_8382_방향전환.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		int T = stoi(br.readLine());
		for(int tc=1; tc<=T; tc++) {
			
			st = new StringTokenizer(br.readLine().trim(), " ");
			min = Integer.MAX_VALUE;
			
			startX = stoi(st.nextToken()); // x
			startY = stoi(st.nextToken()); // y
			endX = stoi(st.nextToken()); // x
			endY = stoi(st.nextToken()); // y
			
			go(startX, startY, true, 0);
			go(startX, startY, false, 0);
			sb.append("#" + tc + " " + min + "\n");
		}
		System.out.println(sb.toString());
		
		br.close();
	} //
}