백준_로봇_1726[Java]

문제 

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

1726번: 로봇

 

풀이

먼저 문제를 보고

이동 횟수뿐만 아니라 방향 회전 또한 명령에 포함해야 했기 때문에

이전에 풀었던 길찾기 같은 문제보다 살짝 더 까다로울 거란 생각이 들었다. 

 

처음 든 생각이 '목적지에 도달할 수 있는 모든 길을 찾은 후 최소 명령 횟수를 구하면 되겠다'싶어서

DFS로 도전했었다. 

 

하지만 답이 나오지 않았고,,,,

다른 블로그를 참고해보니 모두 BFS로 풀고 있었다. 그래서 결국은 BFS로 도전 !

( DFS로도 풀릴텐데 내가 빠트린 것이 있었을 것이다.. 따흑 )

 

* 주의할 점

1. 방향 90도 회전 시 명령은 1회 추가되지만 방향 180도 회전 시에는 명령이 2회 추가된다. 

2. 한번에 최대 3칸의 이동을 할 수 있다. 따라서 한 칸 한 칸 이동 가능한지 확인할 필요가 있다.

    이 때 2칸 이동이 불가능한 상태라면 (벽이 있거나 장외로 떨어진다거나) 3칸 이동도 불가능한 것이다. 

3. 방문한 위치인지 확인하는 배열이 필요하다. 이때 배열은 x좌표와 y좌표의 값과 함께 방향값을 표시할 수 있는 3차원 배열로 선언한다.

4. 로봇 객체(Pair)에 현재 로봇이 이동하는데 쓰인 명령의 갯수를 담는다. 

 

* 칸 이동과 방향전환을 각각 세어준다. 

* 3,4번이 내가 풀었던 방법(BFS)과의 차이점이었다.

 

코드

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

public class Main {
	static int M, N;
	static int[][] factory;
	static Pair start, end;
	
	// 동 서 남 북 
	static int[] dx = {0, 0, 1, -1};
	static int[] dy = {1, -1, 0, 0};
	
	static int result;
	static boolean[][][] visit;
	
	static class Pair{
		int x;
		int y;
		int dir;
		int cnt;
		
		Pair(int x, int y, int dir, int cnt){
			this.x = x;
			this.y = y;
			this.dir = dir;
			this.cnt = cnt;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		M = sc.nextInt();
		N = sc.nextInt();
		
		factory = new int[100][100];
		visit = new boolean[100][100][5];
		
		for(int i = 1; i <= M; i++) {
			for(int j = 1; j <= N; j++) {
				factory[i][j] = sc.nextInt();
			}
		}
		
		int startX, startY, startDir;
		startX = sc.nextInt();
		startY = sc.nextInt();
		startDir = sc.nextInt();
		start = new Pair(startX, startY, startDir, 0);
		
		int endX, endY, endDir;
		endX = sc.nextInt();
		endY = sc.nextInt();
		endDir = sc.nextInt();
		end = new Pair(endX, endY, endDir, 0);
		
		visit[startX][startY][startDir] = true; // 시작위치 방문기록 
		
		solution();
		
		sc.close();
	}
	
	
	private static  void solution() {
		Queue<Pair> q = new LinkedList<Pair>();
		q.add(start);

		while(!q.isEmpty()) {
			Pair curPair= q.poll();
			int curDir = curPair.dir;
			int curX = curPair.x;
			int curY = curPair.y;
			int curCnt = curPair.cnt;
			
			if(curX == end.x && curY == end.y && curDir == end.dir) {
				System.out.println(curCnt);
				return;
			}
			
			// 칸 이동 
			for(int i = 1; i <= 3; i++) { 
				// 이동할 수 있는 칸수를 모두 확인하면서 큐에 넣어준다. 
				int nextX = curX + dx[curDir-1] * i;
				int nextY = curY + dy[curDir-1] * i;
				
				if(nextX > M || nextY > N || nextX <= 0 || nextY <= 0) {
					// 장외 
				}else {
					if(factory[nextX][nextY] == 0) { // 이동 가능 
						
						if(!visit[nextX][nextY][curDir]) {
							visit[nextX][nextY][curDir] = true;
							q.add(new Pair(nextX, nextY, curDir, curCnt+1));
						}
					} else { // 그 이상의 칸으로 이동 불가 
						break;
					}
				}
 			}
			
			// 회전 
			for(int i = 1; i <= 4; i++) { 
				if(curDir != i && !visit[curX][curY][i]) {
					visit[curX][curY][i] = true;
					if((curDir == 1 && i == 2 )|| (curDir == 2 && i == 1 ) || (curDir == 3 && i == 4) ||(curDir == 4 && i == 3)) {
						q.add(new Pair(curX, curY, i, curCnt+2));
					}else {
						q.add(new Pair(curX, curY, i, curCnt+1));
					}
					
					
				}
				
			}
			
		}
		
	}

}

 

항상 느끼는 거지만 나는 메소드가 어떤 반환 값을 가질지 그리고 메소드를 빠져나오는 방식을 생각할 때 어려움을 겪는 것 같다.

정답으로 구해야 하는 횟수를 어떻게 반환할 지, 언제 횟수가 추가되어 어떻게 최솟값을 구하는지 ! 

이전 문제들의 풀이 방식을 꼼꼼히 참고하여 문제 별 방식을 익히고 생각하는 연습을 해야겠다.  

 

참고

- 

https://mygumi.tistory.com/241

백준 1726번 로봇 :: 마이구미

- 

https://jaimemin.tistory.com/909

백준 1726번 로봇