[삼성SW기출문제] 14503번 로봇 청소기

1. 문제 링크

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

14503번: 로봇 청소기

 

2. 코드

- 문제 소요 시간: 1시간 10분

from collections import deque

N, M = map(int, input().split())
r, c, d = map(int, input().split())
dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1] # 북, 동, 남, 서
graph = []
for _ in range(N):
    graph.append(list(map(int, input().split())))

q = deque()
answer = 0

def bfs(X, Y, D):
    q.append((X, Y, D))
    global answer

    while q:
        x, y, d = q.popleft()
        count = 0 # 4방향 모두 청소할 수 없을 경우를 위한 count
        if graph[x][y] == 0:
            graph[x][y] = 2 # 1. 현재 위치 청소
            answer += 1

        for i in range(4): # 2. 왼쪽 방향 탐색
            d = d - 1 if d > 0 else 3
            nx, ny = x + dx[d], y + dy[d]
            if graph[nx][ny] > 0: # 2-2. 청소할 수 없는 경우
                count += 1
                continue
            elif graph[nx][ny] == 0: # 2-1. 청소할 수 있는 경우
                q.append((nx, ny, d)) # 회전 및 한 칸 전진
                break

        if count == 4: # 4방향 모두 청소할 수 없으면
            d = d + 2 if d < 2 else d - 2 # 2-3. 후진 위한 방향 전환
            nx, ny = x + dx[d], y + dy[d]
            if graph[nx][ny] == 1: # 2-4. 후진할 수 없으면 작동 종료
                break

            d = d + 2 if d < 2 else d - 2  # 2-3. 방향 원위치
            q.append((nx, ny, d))

    return answer

print(bfs(r, c, d))

 

3. 문제 풀이

- 적용 알고리즘: 구현 + BFS

이 문제는 단순히 주어진 조건만 그대로 구현하면 해결할 수 있는 문제이다. 

• 문제 조건

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

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

처음 풀이할 때 주어진 조건 중에서 2-3을 잘못 해석했다. 로봇청소기가 청소된 곳은 지나갈 수 없다고 생각했었고, 이 때문에 30분정도 소요가 더 되었다..ㅜㅜ

 

4. 추가 요소

- 4방향을 왼쪽으로 회전 시킬 때, 아래와 같은 코드를 작성했었는데, 더 좋은 작성 법이 있어서 소개한다.

1) 내가 작성한 코드

d = d - 1 if d > 0 else 3

2) 추천 코드

d = (d + 3) % 4

 

- 후진하는 코드도 더 좋은 코드가 있어서 마찬가지로 소개한다.

1) 내가 작성한 코드

d = d + 2 if d < 2 else d - 2
nx, ny = x + dx[d], y + dy[d]

2) 추천 코드

x, y 좌표에 방향만 빼주면 반대 방향이 된다.

nx, ny = x - dx[d], y - dy[d]