[백준] 1726 로봇 - 너비우선탐색(BFS) JAVA

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

1726번: 로봇

코드설명

BFS 문제입니다.

 

문제에 대한 이해가 쉽지 않았습니다.

우선 처음에 제가 진행햇던 방법은,

1. Go 방향 이동 1 칸, 2칸, 3칸을 이동한다.

2. GO 방향 이동 후에 명령2. Turn left, Turn right를 각각 실행한다.

 

위의 1번 2번 과정을 순서대로 실행했습니다.

 

하지만, 위의 명령은 독립적으로 실행해야합니다.

문제로직을 설명해보면,

1. 로봇의 초기 위치는 sM, sN, sD (행, 열, 방향)로 읽습니다. 목적지 위치는 eM, eN, eD로 읽습니다.
2. Node 클래스는 시뮬레이션의 상태를 나타내며 현재 행, 열, 방향 및 움직인 횟수 (cnt)를 포함합니다.
3. BFS함수에서는,

   3-1. 먼저 GO 1 2 3 칸을 각각 이동처리하며 큐에 넣습니다. (이떄 벽을 만나면 바로 중단시켜야합니다.)

   3-2. 4가지 방향으로 회전시키며 각각 큐에 넣습니다. (유의해야할점은 문제에서 주어진대로 방향을 구현해야하기에 각각의 방향에 따른것을 Switch함수로 직접 구현해주어야합니다. 처음에 일종의 식을 구해서 할려고했는데, 규칙성을 찾을 수 없었습니다. )

 

Visited[][][] 배열같은경우 Boolean으로 처리하여 진행합니다. 이 같은경우 최소 이동횟수로 하지 않는 이유는 Queue의 cnt는 선입선출이기에 그 이후에 들어오는 경우는 모두 cnt가 더 클것입니다.

 

코드

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 Main {
	
	public static int N, M;
	public static int[][] map;
	public static int[] dx = {0,0,1,-1}; //동, 서, 남, 북
	public static int[] dy = {1,-1,0,0};
	public static int answer = -1;
	public static Node end;
	public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	M = Integer.parseInt(st.nextToken()); //
    	N = Integer.parseInt(st.nextToken()); //
    	map = new int[M][N];
    	
    	for(int i=0;i<M;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0;j<N;j++) {
    			map[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	//로봇의 출발위치 (행 , 열, 바라보는 방향)
    	st = new StringTokenizer(br.readLine());
    	int sM = Integer.parseInt(st.nextToken());
    	int sN = Integer.parseInt(st.nextToken());
    	int sD = Integer.parseInt(st.nextToken());
    	Node start = new Node(sM - 1, sN - 1, sD - 1, 0);
    	
    	//로봇의 도착지점의 위치(행, 열, 바라보는 방향)
		st = new StringTokenizer(br.readLine());
    	int eM = Integer.parseInt(st.nextToken());
    	int eN = Integer.parseInt(st.nextToken());
    	int eD = Integer.parseInt(st.nextToken());
    	end = new Node(eM - 1, eN - 1, eD - 1, 0);
    			
    	simulate(start);
    	
    	System.out.println(answer);
	}
	
	public static void simulate(Node start) {
		boolean[][][] visited = new boolean[M][N][4]; //어처피 같은방향으로 똑같이 들어오는경우 더 빠르게 들어올 수 없다??
		Queue<Node> q = new LinkedList<>();
		q.offer(start);
		visited[start.r][start.c][start.dir] = true; 
		while(!q.isEmpty()) {
			Node temp = q.poll();
			
			if(temp.r == end.r && temp.c == end.c && temp.dir == end.dir) {
				answer = temp.cnt;
				return ;
			}
			
			//현재 향하고 있는 방향으로 1칸, 2칸, 3칸 이동하는경우를 큐에 넣습니다.
			for(int move = 1; move<=3; move++) {
				int nx = temp.r + dx[temp.dir] * move;
				int ny = temp.c + dy[temp.dir] * move;
				
				if(nx < 0 || nx >= M || ny < 0 || ny >= N) continue;
				if(map[nx][ny] == 1) break; //만약 벽을 만난다면 더 이상 이동하지 못한다. 처음에 띄어서 가는줄알았는데, 막히면 더 이상 움직이지 않는다.
				
				if(visited[nx][ny][temp.dir] == false) { //해당 방향이 이미 방문하지 않았다면,
					visited[nx][ny][temp.dir] = true;
					q.offer(new Node(nx, ny, temp.dir, temp.cnt + 1));
				}
				
			}
			
			//직접 방향을 설정해줍니다. 문제에서 주어진대로 동(1) 서(2) 남(3) 북(4) 로 두고 어떤식이 있을까 고민해보았는데
			//직접 방향을 설정해주는게 낫다고 생각합니다.
			//dir에 맞춰서 0 1 2 3 으로 진행합니다.
			
			int leftTurn = 0; int rightTurn = 0; 
			switch(temp.dir) {
				case 0:  //0 (동쪽)에서 왼쪽으로 회전하면 3(북), 오른쪽으로 회전하면 2(남)  
					leftTurn = 3; rightTurn = 2;
					break;
				case 1: //1 (서쪽)에서 왼쪽 회전시 2 (남), 오른쪽으로 회전하면 3 (북)
					leftTurn = 2; rightTurn = 3;
					break;
				case 2: //2 (남쪽)에서 왼쪽 회전시 0 (동), 오른쪽으로 회전하면 1 (서) 
					leftTurn = 0; rightTurn = 1;
					break;
				case 3: //3. (북쪽)에서 왼쪽 회전시 1 (서), 오른쪽으로 회전하면 0 (동)
					leftTurn = 1; rightTurn = 0;
					break;
			}
			
			if(visited[temp.r][temp.c][leftTurn] == false) {
				visited[temp.r][temp.c][leftTurn]= true;
				q.offer(new Node(temp.r, temp.c, leftTurn, temp.cnt + 1));
			}
			if(visited[temp.r][temp.c][rightTurn] == false) {
				visited[temp.r][temp.c][rightTurn]= true;
				q.offer(new Node(temp.r, temp.c, rightTurn, temp.cnt + 1));
			}
			
		}
	}
}

class Node{
	int r;
	int c;
	int dir;
	int cnt;
	public Node(int r, int c, int dir, int cnt) {
		this.r=r;
		this.c=c;
		this.dir=dir;
		this.cnt=cnt;
	}
}