로봇 [백준 1726][JAVA][골드 4][BFS]

 

[광고 누르면 오늘의 행운 상승!!]

https://www.acmicpc.net/problem/1726

1726번: 로봇

1. 참고사항

- 방향이 시계방향이나 반시계방향이 아니다. (북동남서 OR 북서남동) X (동서남북) O
- 1,2,3칸 이동한 로봇과 0칸 이동하고 좌,우로 방향전환한 로봇을 큐에 넣는다.

2. 구현
- 시작 위치와 방향, 도착 위치와 방향을 받고 시작위치에서 BFS를 시작한다.
- 로봇의 방향으로 1, 2, 3 칸 이동한 곳을 Q에 넣는다.
- 로봇의 방향에서 좌 우 에 해당하는 뱡향을 Q에 넣는다.
- 목적지에 도달하면 ans를 갱신한다.

package Study9;

import java.io.*;
import java.util.*;

public class 로봇 {
	static class Robot{
		int row, col, dir, cnt;
		public Robot(int row, int col, int dir, int cnt) {
			this.row = row;
			this.col = col;
			this.dir = dir;
			this.cnt = cnt;
		}
	}
	public static int[] dx = {0,0,1,-1};
	public static int[] dy = {1,-1,0,0};
	static int[][] map;
	static boolean[][][] visit;
	static int R,C,ans = Integer.MAX_VALUE;
	static int SROW,SCOL,SDIR,FROW,FCOL,FDIR;
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		
		map =  new int[R][C];
		visit = new boolean[4][R][C];
		
		for (int i = 0; i < R; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < C; j++) {
				map[i][j] =  Integer.parseInt(st.nextToken());
			}
		}
		st = new StringTokenizer(br.readLine());
		SROW = Integer.parseInt(st.nextToken())-1;
		SCOL = Integer.parseInt(st.nextToken())-1;
		SDIR = Integer.parseInt(st.nextToken())-1;
		
		st = new StringTokenizer(br.readLine());
		FROW = Integer.parseInt(st.nextToken())-1;
		FCOL = Integer.parseInt(st.nextToken())-1;
		FDIR = Integer.parseInt(st.nextToken())-1;
		
		bfs();
		System.out.println(ans);
		
	}
	private static void bfs() {
		Queue<Robot> q = new LinkedList<>();
		q.add(new Robot(SROW,SCOL,SDIR,0));
		visit[SDIR][SROW][SCOL] = true;
		
		while(!q.isEmpty()) {
			
			Robot robot = q.poll();
			if(robot.row == FROW && robot.col == FCOL && robot.dir == FDIR) {
				
				ans = Math.min(ans, robot.cnt);
				continue;
			}
			
			//로봇의 뱡향으로 3칸 전진
			for (int j = 1; j <= 3; j++) {
				int nx = robot.row + dx[robot.dir]*j;
				int ny = robot.col + dy[robot.dir]*j;
				
				if(nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
			
				if(map[nx][ny] == 1) break;
				
				if(visit[robot.dir][nx][ny]) continue;
				else {
					visit[robot.dir][nx][ny] = true;
					q.add(new Robot(nx,ny,robot.dir,robot.cnt+1));
				}
			}
			//동서남북
			//0123
			int left = 0 , right = 0;
			//우회전 or 좌회전이면 add
			switch(robot.dir) {
				case 0: left = 3; right = 2; break;
				case 1: left = 2; right = 3; break;
				case 2: left = 0; right = 1;break;
				case 3: left = 1; right = 0;break;
			}
			
			if(!visit[left][robot.row][robot.col]) {
				visit[left][robot.row][robot.col] = true;
				q.add(new Robot(robot.row,robot.col,left,robot.cnt+1));
			}
			
			if(!visit[right][robot.row][robot.col]) {
				visit[right][robot.row][robot.col] = true;
				q.add(new Robot(robot.row,robot.col,right,robot.cnt+1));
			}
		}
	}
}