[백준] 1726. 로봇 (자바 JAVA)

[ 문제 ]  [백준] 1726. 로봇 (자바 JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/1726

1726번: 로봇

 

 

 

---

# 접근 방법 및 풀이 

 

• 출발지점에서 도착지점까지 최단거리로 움직이는 것이기 때문에 BFS로 풀었다. 
• 초기 궤도는 map[][]으로 입력받고, 출발지점과 끝지점 입력을 받는다. 
• 이때 입력에서 주어진 방향이 동쪽이 1, 서쪽이 2, 남쪽이 3, 북쪽이 4로 주어지는데, 이게 불편해서 내가 편한대로 방향을 다음과 같이 바꿔주었다. 따라서 입력으로 주어진 값도 아래처럼 바꿔주었다.

  	0 북
  3 서	(r, c)	1 동
  	2 남

• 그리고 큐에 넣을 class를 만들었다. Node class로 r, c, d, cnt로 만들었다. (현재위치, 현재방향, 연산횟수)
• 먼저 명령은 2가지다. 첫번째 명령인 Go k는 하나의 명령에 1,2,3칸을 이동할 수 있으므로 현재 위치에서 1,2,3칸을 다 가보는 것을 떠올렸다.
• 두번째 명령인 Turn dir은 현재 내 위치에서 왼쪽으로 90도, 오른쪽으로 90도 회전을 해서 방향을 바꿔보는 것이다.
• 그래서 내가 처음 생각한건, 현재 위치에서 내 현재 방향으로 1, 2, 3칸 가보는 것과 현재 위치에서 방향만 바꿔서 큐에 넣는 것이다.
• 여기서 중요한건 visit배열이다. 보통 visit을 map과 같이 [][]로 만들지만 여기선 3차원 배열 visit[][][4]로 만들어야한다. 같은 좌표 r, c라도 4가지 방향 모두 해당 map[r][c]를 올 수 있고, 도착지점에 도착했을 때 도착지점의 방향까지도 일치해야하기 때문에 먼저 도착한 것이 답이 아닐 수 있다.
• 예를들어, 아래와 같은 상황이라고 한다면,

• 	↓Node(1, 1, 남, 2)
  	도착지점 2, 1 도착방향: 남쪽
  	↑Node(3, 1, 북, 1)

• ↑Node(3, 1, 북, 1) 북쪽 방향을 가진 node가 cnt = 2일때 먼저 도착지점에 도착하지만, 도착방향이 남쪽이므로,Turn dir 연산 90도 회전을 2번을 해야 완벽히 일치한다. 따라서 총 연산횟수는 4번이 될것이다.
• ↓Node(1, 1, 남, 2) 는 cnt = 3 일때 도착하고, 도착지점의 방향이 이미 남쪽으로 같기때문에 Turn dir연산을 할 필요 없이 총 연산 횟수는 3이다. 따라서 최소 연산 횟수는 3이 답이 될 것이다.
• 따라서 visit배열을 3차원 배열로 만들어준다.
• 출발 위치를 큐에 넣고 BFS를 시작한다.
• 현재 내 방향에서 다른 방향으로 바꿀때 90도 연산을 1번하느냐, 2번하느냐 체크를 잘 해주어야한다.
• 도착지점에 도착했을때 바로 빠져나오는 것이 아니라, 도착지점의 방향까지 값이 일치해야하므로 방향까지 더한 연산을 더해줘서 최소값을 계산한 값이 정답이므로 continue를 했다.
• 또한 1,2,3 칸 이동시 도중에 1이 있으면 해당 칸은 건너가지 못하므로 break해서 빠져나와야한다.
• 어디서 continue를 할지 break를 할지가 분기의 중요점이다.
• 그러나 visit[][][]할 때는 이미 방문했다고 break로 빠져나오는 것이 아니라, continue를 해야한다.

• 	3
  	3  2
  	2  1
  	1

• 예를 들어, 북쪽으로 향한다고 했을때 같은방향으로 1, 2, 3칸 이동하면 위 그림과 같이 겹치기 때문에 도중에 break 하면 안된다. 설명이 좀 개떡같지만 암튼 저 그림대로 생각했다.
• 자세한건 코드를 보면 더 이해가 쉬울 것 같다.

 

# 주의할 점 

 

• M, N 주의할 것 보통 N과 M으로 행 열 하지만 입력이 M이 행 N이 열이다.
• 해당 방향으로 1칸, 2칸 3칸 갈때 도중에 1이 있다면 더 갈 수 없고 break;
• 방향 변경시 왼쪽으로 90도, 오른쪽으로 90도 이동할 수 있기때문에 그에 따른 연산횟수 체크 해야함. (1번 / 2번)
• 그리고 Go K 할때 visit[nr][nc][nd]는 break하는 것이 아니라 continue해야함. 방문지점 넘어서도 갈 수 있음.

 

JAVA 코드

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 {
	static int dr[] = {-1, 0, 1, 0};
	static int dc[] = {0, 1, 0, -1};
	static class Node{
		int r, c, d, cnt;
		public Node(int r, int c, int d, int cnt) {
			this.r = r;
			this.c = c;
			this.d = d;
			this.cnt = cnt;
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		int M = Integer.parseInt(st.nextToken()); //행
		int N = Integer.parseInt(st.nextToken()); //열
		int map[][] = new int[M][N];
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		st = new StringTokenizer(in.readLine());
		int startR = Integer.parseInt(st.nextToken())-1;
		int startC = Integer.parseInt(st.nextToken())-1;
		int currD = Integer.parseInt(st.nextToken());
		currD = (currD == 4 || currD == 1)? currD%4 : ((currD == 3)? 2 : 3);
		st = new StringTokenizer(in.readLine());
		int endR = Integer.parseInt(st.nextToken())-1;
		int endC = Integer.parseInt(st.nextToken())-1;
		int endD = Integer.parseInt(st.nextToken());
		endD = (endD == 4 || endD == 1)? endD%4 : ((endD == 3)? 2 : 3);
		int ans = Integer.MAX_VALUE;
		boolean visit[][][] = new boolean [M][N][4];
		Queue<Node> queue = new LinkedList<Node>();
		visit[startR][startC][currD] = true;
		queue.add(new Node(startR, startC, currD, 0));
		while(!queue.isEmpty()) {
			Node node = queue.poll();
			if(node.r == endR && node.c == endC) {
				if(node.d != endD) {
					int dif = Math.abs(node.d - endD);
					node.cnt = (dif==1 || dif == 3)? node.cnt+1 : node.cnt+2;
				}
				ans = Math.min(ans, node.cnt);
				continue;
			}		
			for (int i = 0; i < 4; i++) {
				int nd = (node.d + i) % 4;
				int dif = Math.abs(node.d - nd);
				int cnt = node.cnt;
				if(dif == 0) {
					for (int j = 1; j <= 3; j++) {
						int nr = node.r + (dr[nd]*j);
						int nc = node.c + (dc[nd]*j);
						if( nr < 0 || nc < 0 || nr >= M || nc >= N || map[nr][nc] == 1)
							break;
                        if(visit[nr][nc][nd])
                            continue;
						visit[nr][nc][nd] = true;
						queue.add(new Node(nr, nc, nd, cnt+1));
					}
				}
				else {
					if(visit[node.r][node.c][nd])
						continue;
					cnt = (dif==1 || dif == 3)? cnt+1 : cnt+2;
					visit[node.r][node.c][nd] = true;
					queue.add(new Node(node.r, node.c, nd, cnt));
				}
			}
		}
		System.out.println(ans);
	}
}

 

 

REVIEW

근래에 푼 문제중에 정말 고려할 점이 많은 문제였다. 백준 질문검색 보고 어디서 잘못된건지 한참을 본 후에야 깨달았다. 주의할 점이 정말 정말 많은 문제.. 이거 골드 2정도는 되지않나,, 이거 왜 4냐..?