[알고리즘] 로봇 청소기 (백준 14503번)

14503번: 로봇 청소기

 시뮬레이션 문제다. 처음에 '되돌아 온다' 는 문장만 보고 DFS로 백트랙킹 하는 건가 했었는데 아닌듯 해서 그냥 BFS로 풀었다.

 

Solution

 사실 완전 탐색이랑은 관련이 없다. 조건에 맞는 한 방향으로만 계속 나아가기 때문이다. 다만 문제에서 헷갈렸던 부분이 있었다.

네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

 처음에 바라보는 방향을 유지하면서 후진을 한다면 이 때까지 온 경로 그대로 되돌아간다는 뜻이라고 처음에 이해했는데 잘 생각해보니 아니였다.  

 만약 ↑→↓ 이런 식으로 방향이 변하면서 진행했다고 쳤을 때, 후진할 시 ↓→↑ 이렇게 방향 유지를 하면서 가는게 아니라 ↓↓↓ ... 이렇게 한 방향으로만 유지하면서 후진해야하기 때문에 벽에 부딪힐 수 있다.

 

 그것만 고려하면 나머지는 계속 현재 방향의 왼쪽 방향의 블록을 보고 청소 가능하면 탐색, 아니면 다시 왼쪽으로 회전하면 된다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {

	static boolean visited[][];
	static int count = 0;

	public static void solution() throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		String[] list = br.readLine().split(" ");
		int N = Integer.parseInt(list[0]);
		int M = Integer.parseInt(list[1]);


		list = br.readLine().split(" ");

		int start_x = Integer.parseInt(list[0]);
		int start_y = Integer.parseInt(list[1]);
		int start_dir = Integer.parseInt(list[2]);

		int map[][] = new int[N][M];

		for(int i = 0;i < N;i++)
		{
			list = br.readLine().split(" ");

			for(int j = 0;j < M;j++)
				map[i][j] = Integer.parseInt(list[j]);
		}

		visited = new boolean[N+1][M+1];

		Queue<Position> queue = new LinkedList<>();
		queue.offer(new Position(start_x, start_y, start_dir, 1));
		visited[start_x][start_y] = true;

		while (!queue.isEmpty())
		{
			Position now = queue.poll();
			int dir = now.dir;

			count = now.count;

			boolean go_back = true;

			for(int i = 0;i < 4;i++)
			{
				dir = turnLeft(dir);

				int next[] = getFront(now.x, now.y, dir);

				if(0 <= next[0] && next[0] < N && 0 <= next[1] && next[1] < M)
				{
					if(!visited[next[0]][next[1]] && map[next[0]][next[1]] == 0)
					{
						visited[next[0]][next[1]] = true;
						queue.offer(new Position(next[0], next[1], dir,now.count + 1));
						go_back = false;
						break;
					}
				}
			}

			//네방향 모두 갈 수 없는 경우 뒤돌아가야함
			if(go_back)
			{
				int next[] = getBack(now.x, now.y, now.dir);
				if(0 <= next[0] && next[0] < N && 0 <= next[1] && next[1] < M)
				{
					//벽이 아닌 경우에만
					if (map[next[0]][next[1]] == 0)
						queue.offer(new Position(next[0],next[1], now.dir, now.count));
				}
			}
		}

		bw.write(count+"");

		bw.close();
		br.close();
	}

	public static int turnLeft(int dir)
	{
		if(dir == 0)
			return 3;
		return dir - 1;
	}

	public static int[] getBack(int x, int y, int dir)
	{
		int next[] = {x, y};

		//북
		if(dir == 0)
			next[0] ++;
			//동
		else if(dir == 1)
			next[1] --;
			//남
		else if(dir == 2)
			next[0] --;
		else
			next[1] ++;
		return next;
	}

	public static int[] getFront(int x, int y, int dir)
	{
		int next[] = {x, y};

		//북
		if(dir == 0)
			next[0] --;
		//동
		else if(dir == 1)
			next[1] ++;
		//남
		else if(dir == 2)
			next[0] ++;
		else
			next[1] --;
		return next;
	}


	static class Position{
		int x, y, dir;
		int count;

		public Position(int x, int y, int dir, int count) {
			this.x = x;
			this.y = y;
			this.dir = dir;
			this.count = count;
		}
	}


	public static void main(String[] args) {
		try
		{
			solution();
		}
		catch (Exception e)
		{
			e.printStackTrace();
		}
	}

}