[SWEA] 8382 - 방향전환

[문제링크]

SW Expert Academy

 

0. state 클래스로 정보를 관리 (x좌표, y좌표, 이전이동, 이동횟수)

 

1. bfs처럼 진행하되, 항상 목표지점으로 다가가는 이동이 최적의 이동이다

  - 현재 좌표와 목표좌표를 비교, 나아가야 할 방향을 결정한다

 

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

public class Solution{
	
	static class state {
		public int x,y,prev,cost;
		public state(int x, int y, int prev, int cost) {
			super();
			this.x = x;
			this.y = y;
			this.prev = prev;
			this.cost = cost;
		}
	}
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int tc = pint(br.readLine());
		for (int testcase = 1; testcase <= tc; testcase++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int sx = pint(st.nextToken());
			int sy = pint(st.nextToken());
			int dx = pint(st.nextToken());
			int dy = pint(st.nextToken());
			
			Queue<state>qu=new LinkedList<>();
			
			if(sx==dx && sy==dy) {
				sb.append("#").append(testcase).append(" ").append(0).append("\n");
				continue;
			}
			
			if(sx<dx)qu.offer(new state(sx+1,sy,1,1));
			else qu.offer(new state(sx-1,sy,1,1));
			if(sy<dy)qu.offer(new state(sx,sy+1,2,1));
			else qu.offer(new state(sx,sy-1,2,1));
			
			while(true) {
				state cur = qu.poll();
				System.out.println(cur.x+" "+cur.y);
				if(cur.x==dx && cur.y==dy) {
					sb.append("#").append(testcase).append(" ").append(cur.cost).append("\n");
					break;
				}
				
				if(cur.prev==2) {
					if(cur.x<dx)qu.offer(new state(cur.x+1, cur.y, 1, cur.cost+1));
					else qu.offer(new state(cur.x-1, cur.y, 1, cur.cost+1));
				}
				else {
					if(cur.y<dy)qu.offer(new state(cur.x, cur.y+1, 2, cur.cost+1));
					else qu.offer(new state(cur.x, cur.y-1, 2, cur.cost+1));
				}
				
			}
		}System.out.println(sb);
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면