Inor

[백준] 14503번 로봇 청소기 본문

Algorithm/백준

[백준] 14503번 로봇 청소기

Inor 2017. 11. 6. 12:27

 로봇 청소기를 회전 시키며 이동시키고 이동한 구역을 청소하는 방식으로 프로그램이 실행되도록 하는 알고리즘 문제 입니다. 저는 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;

		}

	}

}


'Algorithm > 백준' 카테고리의 다른 글

[백준] 5427번 불  (0) 2017.11.06
[백준] 2468번 안전 영역  (0) 2017.11.06
[백준] 14500번 테트로미노  (0) 2017.11.06
[백준] 7576번 토마토  (0) 2017.11.06
[백준] 14502번 연구소  (0) 2017.11.06
[백준] 14503번 로봇 청소기  (3) 2017.11.06
3 Comments
  • 프로필사진 Dong 2017.12.04 02:01 안녕하세요 이거 소스 돌려보고 싶은 학생인데요
    맵 크기랑 로봇위치 바라보는 방향을 어떻게 대입해야하나요?
    가령 맵크기가 5X5고 북쪽을 바라보고있다면 0,-1 인가요? 마지막 curDirection은 잘모르겠습니다.
  • 프로필사진 Inor 2017.12.04 16:26 신고 입력 받는 방법은 문제 링크를 찾아 가시면 확인할 수 있습니다!!

    curDirection은 현재 로봇이 바라보고 있는 방향을 의미하는 변수입니다. 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽을 바라보고 있는 것 입니다.
    두개의 switch 문에서 curDirection을 사용하는데, 첫번째 switch문에서 curDirection을 기준으로 잡고 왼쪽으로 회전 했을때 로봇이 바라보는 위치를 curDirection에 다시 설정해줬습니다. 예를 들면, curDirection이 0 일 경우에는 북쪽을 바라보는 상황이고, 왼쪽으로 회전하면 서쪽을 바라보게 되고 curDirection 값은 3으로 초기화됩니다.
    초기화 이후에 dRow, dCol을 사용하는데 이것은 현재 로봇이 위치하고있는 좌표이고, nRow와 nCol은 현재 로봇이 바라보는 방향(curDirection)을 기준으로 로봇이 이동할 좌표입니다. 첫번째 switch 문에서 directions 배열의 인자를 directions[curDirections][0]로 했으면 좋았을텐데 제가 명확하게 표시 못한 점 죄송합니다!!ㅎㅎ 혹시 설명이 부족하거나 더 궁금하신 점 있으시면 추가로 질문해주세요 ~
  • 프로필사진 Dong 2017.12.04 22:26 아 감사합니다~!
댓글쓰기 폼