백준 14503 로봇청소기(Python, C++)

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

14503번: 로봇 청소기

로봇 청소기가 청소 가능한 영역을 찾아내는 문제. 시뮬레이션으로 직접 하나하나 해보면 된다.

 

백준 14503 로봇청소기 풀이

로봇 청소기는 다음과 같이 작동한다.

1. 현재 위치를 청소한다.
2. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 탐색을 진행한다.
   1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
   2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
   3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
   4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.

 

 

세로 크기 N, 가로 크기 M이 주어지고

(R, C)가 현재 위치, D가 현재 방향이 된다.

 

일단 입력받아야 할 정보를 모두 입력받는다.

n, m = map(int, input().split())
r, c, d = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(n)]

 

방향을 옮기면서 판단을 하기 위한 dx, dy 리스트와 방문 표시를 하기 위한 visited 리스트도 만들어준다.

dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1]
visited = [[False] * m for _ in range(n)]

 

출발 위치는 방문표시를 해주고, 청소 횟수는 1부터 시작한다(초기 위치는 이미 청소한 상태이다).

visited[r][c] = True
clean_count = 1

 

반복문을 돌리며 방향을 찾는다.

while True:
    for i in range(4):
        left = (d - i + 3) % 4
        rLeft, cLeft = r+dx[left], c+dy[left]
        if not visited[rLeft][cLeft] and maps[rLeft][cLeft] == 0:
            visited[rLeft][cLeft] = True
            r, c, d = rLeft, cLeft, left
            clean_count += 1
            break
    else:
        back = (d+2) % 4
        rBack, cBack = r + dx[back], c + dy[back]
        if maps[rBack][cBack] == 0:
            visited[rBack][cBack] = True
            r, c, d = rBack, cBack, d
        else:
            break

 

처음 나오는 i 변수 for문에서는 문제의 조건대로 현재 방향의 왼쪽을 탐색한다.

 

dx, dy의 구조를 보면,

  (dx[0], dy[0]) == (-1, 0) -> 북쪽

  (dx[1], dy[1]) == (0, 1)  -> 동쪽

  (dx[2], dy[2]) == (1, 0)  -> 남쪽

  (dx[3], dy[3]) == (0, -1) -> 서쪽

 

순으로 방향을 가리키게 된다.

문제의 입력에서

 

둘째 줄에 로봇 청소기가 있는 칸의 좌표 (r, c)와 바라보는 방향 d가 주어진다. d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽을 바라보고 있는 것이다.

 

라고 했으므로, 기존 방향이 서쪽(3)이라면 왼쪽을 보면 남쪽(2), 남쪽에서 또 왼쪽을 보면 동쪽(1).. 순으로 -1을 해가면서 현재 방향의 왼쪽을 볼 수 있다.

 

문제는 북쪽에서 서쪽을 볼 때인데, 0에서 시작해서 인덱스를 -1씩 줄여나가도 탐색은 가능하다(파이썬의 리스트는 음수 인덱스로 뒤부터 탐색하는 게 가능하다). 하지만 현재 나의 방향을 계속 저장해놓아야 하는 것이 문제이다. 현재 나의 방향은 0, 1, 2, 3 중 하나로만 저장되어야 하기 때문이다.

 

그래서 

left = (d - i + 3) % 4

이러한 방법을 사용했다. 현재 나의 방향이 북쪽(0)이라면, 순서대로 i를 뺀 후의 값 (0, -1, -2, -3)에 3을 더하고 (3, 2, 1, 0) 4를 나누게 되면 서쪽(북쪽의 왼쪽)부터 순서대로 왼쪽을 탐색하게 된다.

 

 

이후 현재 내가 보는 방향(r, c)의 왼쪽(rLeft, cLeft)을 구해놓고 변수로 지정한다.

rLeft, cLeft = r+dx[left], c+dy[left]

 

방문한 적이 없고(visited가 False) 청소가 가능한 구역 (maps == 0)이라면 그 위치로 내 자리를 옮기고 지금 방향을 저장한다. 청소 횟수를 1 증가시킨 뒤 반복문을 탈출한다.

        if not visited[rLeft][cLeft] and maps[rLeft][cLeft] == 0:
            visited[rLeft][cLeft] = True
            r, c, d = rLeft, cLeft, left
            clean_count += 1
            break

 

만약 반복문을 탈출하지 못했다면 뒤로 갈 수 있는지 판단해야 한다.

    else:
        back = (d+2) % 4
        rBack, cBack = r + dx[back], c + dy[back]
        if maps[rBack][cBack] == 0:
            visited[rBack][cBack] = True
            r, c, d = rBack, cBack, d

 

위의 left 변수와 같은 이유로 back도 나머지를 이용해 구한 뒤 저장했다.

만약 나의 뒤가 0이라면 그곳으로 자리를 이동하고 위치 또한 이동시킨다

(문제 조건에 따라 방향은 움직이지 않고, 방문 여부에 상관없이 이동시킨다).

 

 

위 2개의 조건에 모두 해당되지 않는다면 while문을 탈출한 뒤 청소 횟수를 출력한다.

        else:
            break
print(clean_count)

 

전체 코드를 보면 다음과 같다.

n, m = map(int, input().split())
r, c, d = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(n)]

dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1]
visited = [[False] * m for _ in range(n)]

visited[r][c] = True
clean_count = 1

while True:
    for i in range(4):
        left = (d - i + 3) % 4
        rLeft, cLeft = r+dx[left], c+dy[left]
        if not visited[rLeft][cLeft] and maps[rLeft][cLeft] == 0:
            visited[rLeft][cLeft] = True
            r, c, d = rLeft, cLeft, left
            clean_count += 1
            break
    else:
        back = (d+2) % 4
        rBack, cBack = r + dx[back], c + dy[back]
        if maps[rBack][cBack] == 0:
            visited[rBack][cBack] = True
            r, c, d = rBack, cBack, d
        else:
            break

print(clean_count)

 

C++ 코드

동작원리는 Python과 동일하다. 단 for ~ else 구문은 C++에 없기 때문에 can_spin, can_back 변수로 회전할 수 있는지와 뒤돌수 있는지를 판단했다.

#include<iostream>

using namespace std;


int main(){
	int n, m, r, c, d;
	int dx[4] = {-1, 0, 1, 0};
	int dy[4] = {0, 1, 0, -1};
	
	cin >> n >> m;
	cin >> r >> c >> d;

    bool visited[50][50] = {false,};
    int maps[50][50];
    
    int temp;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> temp;
			maps[i][j] = temp;
		}
	}

	visited[r][c] = true;
	int clean_count = 1;

	while (true) {
		bool can_spin = false;
		for (int i = 0; i < 4; i++) {
			int left = (d - i + 3) % 4;
			if (visited[r+dx[left]][c+dy[left]] == false && maps[r+dx[left]][c+dy[left]] == 0) {
				visited[r+dx[left]][c+dy[left]] = true;
				r = r+dx[left];
				c = c+dy[left];
				d = left;
				can_spin = true;
				++clean_count;
				break;
			}
		}

		bool can_back = false;
		if (can_spin == false) {
			int back = (d+2)%4;
			if (maps[r+dx[back]][c+dy[back]] == 0) {
				can_back = true;
				visited[r+dx[back]][c+dy[back]] = true;
				r = r+dx[back];
				c = c+dy[back];
			}
		}

		if (can_spin == false && can_back == false) {
			break;
		}
	}
	cout << clean_count << endl;
	return 0;
}

 

느낀 점

이 문제는 시뮬레이션 중에서도 쉬운 편에 속한다.

DFS, BFS나 백트래킹과 같은 알고리즘 개념이 필요한 문제도 있지만 결국 시뮬레이션은 주어진 조건대로 빠르게 구현하는 시간싸움이기 때문에 꾸준한 연습을 통해 실력을 올리는 것이 중요할 것 같다.