[swexpert] 8382. 방향전환 (구현, java)

상하 와 좌우를 번갈아 이동해야된다.

visited 배열을 3차원으로 사용했다. 마지막은 인덱스는 가로, 세로 중 어디로 이동했냐를 가르킨다.

 

테스트케이스 45개만 통과되는 경우 시작점 = 도착점으로 주어져서 답이 0인 것을 처리해주지 않아서 그렇다.

 

예외로 0을 출력하도록 구현하면 된다.

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Pos{
	int x,y,dir;

	public Pos(int x,int y,int dir) {
		super();
		this.x = x;
		this.y = y;	
		this.dir=dir;
	}
	
}

public class Solution {
	static int t;
	static int y,x,y2,x2;
	static int[][] map;
	static int[] rpos= {-1,1,0,0};//상 하 좌우 
	static int[] cpos= {0,0,-1,1};
	static boolean[][][] vis;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		
		t=sc.nextInt();
		for (int tc = 1; tc <=t; tc++) {
			map=new int[201][201];
			vis=new boolean[201][201][2];
			x=sc.nextInt()+100;
			y=sc.nextInt()+100;
			x2=sc.nextInt()+100;
			y2=sc.nextInt()+100;
			
			if(x==x2 && y==y2) {
				System.out.printf("#%d %d\n",tc,0);
				continue;
			}
			Queue<Pos> q=new LinkedList<Pos>();
			for (int i = 0; i < 4; i++) {
				int yy=y+cpos[i];
				int xx=x+rpos[i];
				if(xx<0 || yy<0 || xx>=201 || yy>=201)continue;
				if(i==0 || i==1) {
					vis[xx][yy][0]=true;//상하
					q.add(new Pos(xx,yy,0));
				}else {
					vis[xx][yy][1]=true;
					q.add(new Pos(xx,yy,1));
				}
				
			}
			
			int answer=0;
			boolean isFinished=false;
			while(q.size()!=0) {
				if(isFinished)break;
				int len=q.size();
				for (int p = 0; p < len; p++) {
					Pos cur=q.poll();
					int y=cur.y;
					int x=cur.x;
					int dir=cur.dir;
					if(y==y2 && x==x2) {
						isFinished=true;
						break;
					}
					int sx=2;
					int sy=4;
					if(dir==1) {//위아래 이동시키기
						sx=0;
						sy=2;
					}
					for (int k = sx; k < sy; k++) {
						int yy=y+cpos[k];
						int xx=x+rpos[k];
						if(xx<0 || yy<0 || xx>200 || yy>200) {
							continue;
						}
						if(vis[xx][yy][1-dir])continue;
						vis[xx][yy][1-dir]=true;
						
						q.add(new Pos(xx,yy,1-dir));
						
					}
				}
				answer+=1;
			}
			
			System.out.printf("#%d %d\n",tc,answer);
		} 
		
	}
}