[백준] 1726 로봇

1. 문제

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

1726번: 로봇

생각없이 풀기 좋은 시뮬 문제

생긴게 삼성문제 같은데 올림피아드 문제다

2. 접근방법

최소 횟수로 출발점에서 도착점까지 도착하는 문제

 

고려해야 할 사항들

1. 회전도 하나의 횟수로 친다

2. 회전은 왼쪽 오른쪽만 가능

3. visit처리 안하면 메모리 터짐 ( [방향][row][col]로 3차원 배열로 설정 )

4. 전진은 한 횟수에 1,2,3칸 가능

4-1. 전진 1이 불가능이면 2,3도 불가능

4-2. 전진 1이 방문했더라도 2,3을 갈 수 있음.

 

일반적인 bfs탐색처럼 풀이하되 분기가

1. 왼쪽 방향 변경

2. 오른쪽 방향 변경

3. 전진 1,2,3칸 (예외처리를 break, continue 위 고려사항 맞게 적절히)

인 것만 생각하고 풀이하면 된다.

 

방향이 특이하게 동서남북 순서로 주어진다.

0,1,2,3 으로 생각하고

왼쪽 오른쪽 방향설정시 아이디어로

현재방향이 0 or 1이면 2,3 으로 방향변경

현재방향이 2 or 3이면 0,1 으로 방향변경 해주면 된다.

 

 

3. 자바 코드

package Gold;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class G4_1726로봇 {
	static class node {
		int row;
		int col;
		int dir;

		public node(int row, int col, int dir) {
			this.row = row;
			this.col = col;
			this.dir = dir;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int map[][] = new int[N][M];
		for (int i = 0; i < N; i++)
			map[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		int start[] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		int end[] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		for (int i = 0; i < 3; i++) { // 인덱스 맞추기
			start[i] -= 1;
			end[i] -= 1;
		}

		int dr[] = new int[] { 0, 0, 1, -1 }; //동서남북
		int dc[] = new int[] { 1, -1, 0, 0 };

		boolean visit[][][] = new boolean[4][N][M]; // dir row col

		visit[start[2]][start[0]][start[1]] = true;
		Queue<node> que = new LinkedList<node>();
		que.add(new node(start[0], start[1], start[2]));

		int cnt = 0;
		while (!que.isEmpty()) {
			int size = que.size();
			while (size-- != 0) {
				node now = que.poll();
				if (now.row == end[0] && now.col == end[1] && now.dir == end[2]) {
					System.out.println(cnt);
					return;
				}
				// 왼쪽 오른쪽 직진(1,2,3)
				int left = now.dir > 1 ? 0 : 2;
				int right = now.dir > 1 ? 1 : 3;
				if (!visit[left][now.row][now.col]) {
					que.add(new node(now.row, now.col, left));
					visit[left][now.row][now.col] = true;
				}
				if (!visit[right][now.row][now.col]) {
					que.add(new node(now.row, now.col, right));
					visit[right][now.row][now.col] = true;
				}
				for (int i = 1; i <= 3; i++) {
					int row = now.row + dr[now.dir] * i;
					int col = now.col + dc[now.dir] * i;
					if (row >= N || col >= M || row < 0 || col < 0)
						break;
					if (map[row][col] == 1)
						break;
					if (visit[now.dir][row][col])
						continue;
					que.add(new node(row, col, now.dir));
					visit[now.dir][row][col] = true;
				}
			}
			cnt++;
		}
	}

}

4. 마치며

전진 중간에 break이 들어가야 하는 조건이 재밌었다.