[SWEA]- 8382 방향 전환

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

SW Expert Academy

---

문제

BFS사용하여 최단거리 탐색

---

주의

상,하 & 좌,우 한 묶음으로 보고 방향이 다른 경우에만 Queue에 Add 해줌.

방문체크 잊지말기

---

구현

Queue의 size만큼 묶어서 실행 -> 진행된 count를 구할수있다

---

참고

BFS에서 진행 거리 구하는 방법

1. 객체배열에 cnt값을 저장 -> Add할때 하나씩 늘려줌 

2. Queue size별로 끊어서 거리 체크  -> 나중에 일정거리만큼 되는 좌표값들에대한 계산이 가능해짐 

 

ex BJ아기상어, BJ토마토

---

package basic;

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

public class SWEA방향전환 {
	
	static int res;
	static boolean [][][] visit = new boolean[201][201][2];//방문체크
	static int tx,ty;//타겟지점의 r,c값
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		
		for (int tc = 1; tc <= T; tc++) {
			//input의 범위가 -100~100이니까 +100씩해줘서 0~200으로 만들어줌.
			int r = sc.nextInt()+100;
			int c = sc.nextInt()+100;
			 tx = sc.nextInt()+100;
			 ty = sc.nextInt()+100;
			 visit = new boolean[201][201][2];
			 //bfs시작
			 res = bfs(r,c);
			
			System.out.printf("#%d %d\n",tc,res);
		}

	}
	static int dr[] = {-1,0,1,0};
	static int dc[] = {0,1,0,-1};
	
	private static int bfs(int r, int c) {
		
		Queue <Pos> Q = new LinkedList<>();
		//처음에 모든 방향으로 다 가보는거 넣어줌.
		Q.offer(new Pos(r,c,0));
		Q.offer(new Pos(r,c,1));
		Q.offer(new Pos(r,c,2));
		Q.offer(new Pos(r,c,3));
		//방문체크잊지말기
		visit[r][c][0]=true;
		visit[r][c][1]=true;
		int result = 0;
		
		while(!Q.isEmpty()) {
			//큐 사이즈만큼 묶어서 실행
			int size = Q.size();
			for (int s = 0; s < size; s++) {
				
				Pos now = Q.poll();
				//해당지점에 도착했다면 최단거리 반환
				if(now.r == tx && now.c == ty) {
					return result;
				}
				//4방탐색
				for (int d = 0; d < 4; d++) {
					//내 방향과 다르다면 진행
					if(now.dir %2 != d%2) {
						int nr = now.r + dr[d];
						int nc = now.c + dc[d];
						//경계체크, 방문체크
						if(nr>=0 && nr <=200 && nc>=0 && nc<=200 && !visit[nr][nc][d%2]) {
							//방문체크해주고 add.
							visit[nr][nc][d%2]= true;
							Q.add(new Pos(nr,nc,d));
							
						}
					}
				}
				
			}//큐 사이즈만큼 순회가 끝났다면
			result++;
			
		}
		return result;
	}
	static class Pos{
		int r,c,dir;

		public Pos(int r, int c, int dir) {
			super();
			this.r = r;
			this.c = c;
			this.dir = dir;
		}
		
	}

}