[BOJ] 백준 1726번 로봇 (Java)

#1726 로봇

난이도 : 골드 3

유형 : 그래프 탐색 / BFS

9466번: 텀 프로젝트

▸ 문제

많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 다음과 같이 두 가지이다.

• 명령 1. Go k: k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다.
• 명령 2. Turn dir: dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다.

공장 내 궤도가 설치되어 있는 상태가 아래와 같이 0과 1로 이루어진 직사각형 모양으로 로봇에게 입력된다. 0은 궤도가 깔려 있어 로봇이 갈 수 있는 지점이고, 1은 궤도가 없어 로봇이 갈 수 없는 지점이다. 로봇이 (4, 2) 지점에서 남쪽을 향하고 있을 때,  이 로봇을 (2, 4) 지점에서 동쪽으로 향하도록 이동시키는 것은 아래와 같이 9번의 명령으로 가능하다.

로봇의 현재 위치와 바라보는 방향이 주어졌을 때, 로봇을 원하는 위치로 이동시키고, 원하는 방향으로 바라보도록 하는데 최소 몇 번의 명령이 필요한지 구하는 프로그램을 작성하시오.

▸ 입력

첫째 줄에 공장 내 궤도 설치 상태를 나타내는 직사각형의 세로 길이 M과 가로 길이 N이 빈칸을 사이에 두고 주어진다. 이때 M과 N은 둘 다 100이하의 자연수이다. 이어 M줄에 걸쳐 한 줄에 N개씩 각 지점의 궤도 설치 상태를 나타내는 숫자 0 또는 1이 빈칸을 사이에 두고 주어진다. 다음 줄에는 로봇의 출발 지점의 위치 (행과 열의 번호)와 바라보는 방향이 빈칸을 사이에 두고 주어진다. 마지막 줄에는 로봇의 도착 지점의 위치 (행과 열의 번호)와 바라보는 방향이 빈칸을 사이에 두고 주어진다. 방향은 동쪽이 1, 서쪽이 2, 남쪽이 3, 북쪽이 4로 주어진다. 출발지점에서 도착지점까지는 항상 이동이 가능하다.

▸ 출력

첫째 줄에 로봇을 도착 지점에 원하는 방향으로 이동시키는데 필요한 최소 명령 횟수를 출력한다.

 

문제 풀이  

시작점과 도착점 좌표를 입력 받은 후 BFS 탐색으로 최단거리를 찾아주면 된다. 

 

유의해야 할 점

1. 1,2,3칸을 움직일 때다. 벽의 두께가 1일 경우에는 1칸에서 막혀도 2칸에서는 뚫리게 되는데 이를 잘 방지해줘야 한다.
2. 방향 전환을 할 때다. 90도가 아닌 180도로 전환하는 경우에는 카운트를 2번 세줘야 한다.
3. 그리고 각 방문여부 체크는 단순 좌표만이 아닌 방향도 고려해줘야 한다.

 

풀이 코드 

import java.io.*;
import java.util.*;
public class Main {
	static class Node{
		int x;
		int y;
		int d;
		int cnt;
		
		public Node(int x, int y, int d, int cnt) {
			super();
			this.x = x;
			this.y = y;
			this.d = d;
			this.cnt = cnt;
		}
		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + d;
			result = prime * result + x;
			result = prime * result + y;
			return result;
		}
		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Node other = (Node) obj;
			if (d != other.d)
				return false;
			if (x != other.x)
				return false;
			if (y != other.y)
				return false;
			return true;
		}
		
		
	}
	static BufferedReader br;
	static StringTokenizer st;
	static int n,m;
	static int[][] map;
	static Node start, end;
	static int[] dx = {1, -1, 0, 0};
	static int[] dy = {0, 0, 1, -1};
	public static void main(String[] args) throws IOException{
		br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());
		inputData();
		bfs();
	}
	
	static void bfs() {
		Queue<Node> q = new LinkedList<>();
		boolean[][][] check = new boolean[n][m][4];
		q.add(start);
		check[start.y][start.x][start.d] = true;
		
		while(!q.isEmpty()) {
			Node cur = q.poll();
			int cy = cur.y;
			int cx = cur.x;
			int cd = cur.d;
			int cnt = cur.cnt;
			
			if(isEnd(cur)) {
				System.out.println(cnt);
				return;
			}
			
			// 현재 방향으로 앞으로 3칸
			for(int f=1; f<=3; f++) {
				int nx = cx+dx[cd]*f;
				int ny = cy+dy[cd]*f;
				
				if(nx < 0 || ny < 0 || nx > m-1 || ny > n-1) continue;
				if(check[ny][nx][cd] ) continue;
				if(map[ny][nx] == 0) {
					check[ny][nx][cd] = true;
					q.add(new Node(nx,ny,cd, cnt+1));	
				}else break;
				
			}
			
			// 방향 변환 
			for(int d=0; d<4; d++) {
				if(d == cd || check[cy][cx][d]) continue;
				
				check[cy][cx][d] = true;
				// 동 서 남 북 (0 1 2 3)
				if(isReverse(cd, d)) {
					q.add(new Node(cx,cy,d, cnt+2));
				}else {
					q.add(new Node(cx,cy,d, cnt+1));
				}
			}
		}
	}
	
	static boolean isReverse(int cd, int nd) {
		if((cd == 0 && nd ==1) || (cd ==1 && nd ==0)
				|| ((cd ==2 && nd ==3)) || (cd ==3 && nd ==2)) return true;
		return false;
	}
	
	static boolean isEnd(Node cur) {
		return end.equals(cur);
	}
	
	static void inputData() throws IOException {
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		map = new int[n][m];
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<m; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		st = new StringTokenizer(br.readLine());
		int y = Integer.parseInt(st.nextToken())-1;
		int x = Integer.parseInt(st.nextToken())-1;
		int d = Integer.parseInt(st.nextToken())-1;
		start = new Node(x,y,d,0);
		
		st = new StringTokenizer(br.readLine());
		y = Integer.parseInt(st.nextToken())-1;
		x = Integer.parseInt(st.nextToken())-1;
		d = Integer.parseInt(st.nextToken())-1;
		end = new Node(x,y,d,0);
		
	}
}