[백준] 14503번 로봇 청소기

 로봇 청소기를 회전 시키며 이동시키고 이동한 구역을 청소하는 방식으로 프로그램이 실행되도록 하는 알고리즘 문제 입니다. 저는 DFS를 이용해서 로봇청소기를 이동 시키려고 했습니다. 그러나 코드를 다 만들고나서 들었던 생각은 이건 DFS는 아니고 그냥 단순히 시뮬레이션으로 만든것 같다는 느낌이 들었습니다. DFS를 사용하려고 했다는 것에 큰 의미를 두겠습니다.. 아래는 문제의 링크 입니다.

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

 구현 과정에서 가장 먼저 생각했던 것은 로봇청소기를 회전 시키는 방법과 청소할 구역이 없을때 후진 시키는 방법을 생각하였습니다. 회전의 경우에는 지금 로봇이 바라보고 있는 위치의 값에 따라서 변경해주었습니다. 후진도 마찬가지로 현재 바라보는 방향에서 뒤로 이동 시켰습니다. 이동 시키는 방법은 다음에 이동해야하는 위치(배열의 row, col 값)를 변수에 저장하고 다음 턴에 해당 위치로 이동 시켰습니다. 아래는 완성된 코드 입니다.

import java.util.Scanner;
import java.util.Stack;

public class CleanRobot {
	int[][] map;
	int[][] directions = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
	int curDirection;
	Pair<Integer, Integer> robotLoc;
	Stack<Pair<Integer, Integer>> stack = new Stack<Pair<Integer, Integer>>();
	int row, col;
	int ans = 0;

	void dfs() {
		int dRow, dCol;
		int nRow = -1, nCol = -1;
		int tempCur = curDirection;
		Pair<Integer, Integer> tempPair;

		while (!stack.isEmpty()) {
			
			tempPair = stack.pop();
			dRow = tempPair.x;
			dCol = tempPair.y;
			tempCur = curDirection;
			
			if (map[dRow][dCol] == 0) {
				map[dRow][dCol] = 2;
				ans++;
			}
			
			//왼쪽부터 회전
			for (int i = 0; i < 4; i++) {
				switch (curDirection) {
				case 0: {
					curDirection = 3;
					nRow = dRow + directions[curDirection][0];					
					nCol = dCol + directions[curDirection][1];				
					break;
				}
				case 1: {
					curDirection = 0;
					nRow = dRow + directions[curDirection][0];
					nCol = dCol + directions[curDirection][1];
					break;
				}
				case 2: {
					curDirection = 1;
					nRow = dRow + directions[curDirection][0];
					nCol = dCol + directions[curDirection][1];
					break;
				}
				case 3: {
					curDirection = 2;
					nRow = dRow + directions[curDirection][0];
					nCol = dCol + directions[curDirection][1];
					break;
				}
				}
				if (0 <= nRow && nRow < row && 0 <= nCol && nCol < col) {
					if (map[nRow][nCol] == 0) {
						tempPair = new Pair<Integer, Integer>(nRow, nCol);
						stack.push(tempPair);
						break;
					}
				}
			}
			
			//뒤로 후진
			if (stack.isEmpty()) {
				curDirection = tempCur;
				switch (curDirection) {
				case 0: {
					nRow = dRow + directions[2][0];
					nCol = dCol + directions[2][1];
					break;
				}
				case 1: {
					nRow = dRow + directions[3][0];
					nCol = dCol + directions[3][1];
					break;
				}
				case 2: {
					nRow = dRow + directions[0][0];
					nCol = dCol + directions[0][1];
					break;
				}
				case 3: {
					nRow = dRow + directions[1][0];
					nCol = dCol + directions[1][1];
					break;
				}
				}
				if (map[nRow][nCol] == 1)
					return;
				tempPair = new Pair<Integer, Integer>(nRow, nCol);
				stack.push(tempPair);
			}
		}
	}

	void solution() {
		Scanner s = new Scanner(System.in);

		row = s.nextInt();
		col = s.nextInt();
		int tempRow, tempCol;
		tempRow = s.nextInt();
		tempCol = s.nextInt();
		robotLoc = new Pair<Integer, Integer>(tempRow, tempCol);
		curDirection = s.nextInt();
		map = new int[row][col];
		stack = new Stack<Pair<Integer, Integer>>();
		stack.push(robotLoc);

		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				map[i][j] = s.nextInt();
			}
		}

		dfs();
		
		System.out.println(ans);
	}

	public static void main(String[] args) {
		CleanRobot m = new CleanRobot();
		m.solution();
	}

	class Pair<X, Y> {
		X x;
		Y y;

		public Pair(X x, Y y) {
			this.x = x;
			this.y = y;

		}

	}

}