[삼성 SW Expert Academy] 8382. 방향 전환 [JAVA]

| Problem

※ SW Expert Academy는 문제의 무단 복제를 금지하고 있기 때문에, 기재하지 못한 점 양해 부탁드립니다.

---

| Link

※ 하단의 Link를 클릭해도, 로그인 후 열람이 가능합니다.

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWyNQrCahHcDFAVP&categoryId=AWyNQrCahHcDFAVP&categoryType=CODE

SW Expert Academy

---

| 풀이

1. 가로 또는 세로로 모두 이동해보기
2. bfs 사용해서 이전과 다른 방향으로 이동하면서 찾고자 하는 값 찾기

• 유의사항
• x, y 좌표가 -100 ~ 100 이므로, 배열 사용할 때 + 100 해주기
• visited 배열에서 각 방향에 따른 방문 경우가 다르기 때문에 3차원 배열로 선언 new boolean[201][201][2]

---

| 어려웠던 점

1. 처음 어느 방향과 상관 없기 때문에 다 넣어 놓고 시작했다.
2. 그 때, visited 처리를 [x1][y1] 으로 했어야 했다. 기존에 [nr][nc]로 설정해서 45/50개 fail

---

| 코드

package 알고리즘공부하기;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class 방향전환_8382 {

	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, 1, -1}; // 상하좌우
	static int Tc, x1, x2, y1, y2;
	static int[][] map;
	static Queue<node> q ;
	static boolean[][][] visited ;
	static int answer ;
	private static class node{
		int r,c;
		int direction; // 0 : 세로, 1 : 가로 
		int count;
		node( int r, int c, int direction, int count){
			this.r =r;
			this.c =c;
			this.direction = direction;
			this.count = count;
		}
		
	}
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st ;
		
		st = new StringTokenizer(br.readLine()," ");
		Tc = Integer.parseInt(st.nextToken());
		for( int tc=1; tc<=Tc; tc++) {
			
			st = new StringTokenizer(br.readLine()," ");
			x1 = Integer.parseInt(st.nextToken())+100;
			y1 = Integer.parseInt(st.nextToken())+100;
			x2 = Integer.parseInt(st.nextToken())+100;
			y2 = Integer.parseInt(st.nextToken())+100;
			q = new LinkedList<>();
			
			map = new int[201][201];
			visited = new boolean[201][201][2]; // 가로 방향, 세로방향
			answer = 0;
			
			//1. 첫 이동은 가로 or 세로
			for( int d=0 ;d<4; d++) {
				int nr = x1 + dr[d];
				int nc = y1 + dc[d];
				
				if ( !isIn(nr,nc)) continue;
				// 세로이동이라면
				if ( d == 0 || d == 1 ) {
					visited[x1][y1][0] = true;
					q.add(new node(nr,nc,0,1)); // 0 : 세로
				} 
				// 가로 이동이라면 
				else {
					visited[x1][y1][1] = true;
					q.add(new node(nr,nc,1,1)); // 1 : 가로
				}
			}
			answer = bfs();
			
			System.out.println("#"+tc+" "+answer);
		}
		
	}
	
	private static int bfs() {
		
		while( !q.isEmpty()) {
			node Cur = q.poll();
			int r= Cur.r;
			int c= Cur.c;
			int direction = Cur.direction;
			// 찾으면
			if ( r == x2 && c == y2 ) {
				return Cur.count;
			}
			
			if( direction == 0) { // 이전에 세로로 이동했다면
				for( int d=2; d<4; d++) { // 가로로 이동하기
					int nr = r + dr[d];
					int nc = c + dc[d];
					
					if ( !isIn(nr,nc) || visited[nr][nc][direction ^ 1]) continue;
					
					visited[nr][nc][direction ^ 1] = true;
					q.add(new node(nr,nc,direction ^ 1, Cur.count+1)); // 1 : 가로
				}
			}
			
			else if( direction == 1 ) { // 이전에 가로로 이동했다면
				for( int d=0; d<2; d++) { // 세로로 이동하기
					int nr = r + dr[d];
					int nc = c + dc[d];
					
					if ( !isIn(nr,nc) || visited[nr][nc][direction ^ 1]) continue;
					
					visited[nr][nc][direction ^ 1] = true;
					q.add(new node(nr,nc,direction ^ 1, Cur.count+1)); // 0 : 세로
				}
			}
		}
		return 0;
	}
	
	
	private static boolean isIn(int r, int c) {
		if ( r>=0 && r<201 & c >=0 && c<201) return true;
		return false;
	}
}

---

| 보완할 점

1. 규칙성 찾아서 하는 방법도 있음. 

---