BOJ 14503 로봇청소기 (Python)

문제풀이

풀이과정

문제를 차례대로 따라가 그대로 하라는 대로 하면 풀리는 문제이다. 반시계 방향으로 회전한다는 점과 후진해서 벽을 확인하는 점만 해결한다면 쉽게 풀리는 문제이다.

1. 반시계 방향으로 90도 회전

• direction = (direction + 3) % 4를 이용했다. dx, dy도 북쪽 0, 동쪽 1, 남쪽 2, 서쪽 3 순서대로 정의했고 그렇게 되면 예를 들어 direction이 0일 때 북쪽을 바라보고 있는데 그 다음 탐색 방향은 서쪽이므로 그에 맞게 index가 3으로 변경된다.

2. 후진 확인

• 4가지 방향을 다 탐색했는데도 불구하고 빈 공간이 없다면 마지막으로 후진 가능 여부를 판단한다. 현재 바라보고 있는 방향을 direction이라고 할 때 1번과 마찬가지로 direction = (direction + 2) % 4를 이용하여 아래 코드와 같이 현재 위치의 반대쪽 direction을 확인하면 된다

if exist == False:
    if data[x + dx[(direction + 2) % 4]][y + dy[(direction + 2) % 4]] == 1:
        return

---

Code

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())
a, b, direction = map(int, input().split())

data = []
visited = [[False] * m for _ in range(n)]
visited[a][b] = True

for _ in range(n):
    data.append(list(map(int, input().split())))

result = 1

def bfs(x,y):
    global result
    global direction
        
    queue = deque([(x, y)])

    # 북 동 남 서
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    while queue:
        x, y = queue.popleft()
        exist = False
        for i in range(4):
            direction = (direction + 3) % 4  # 왼쪽 방향으로 이동
            nx = x + dx[direction]
            ny = y + dy[direction]

            if 0 <= nx < n and 0 <= ny < m and data[nx][ny] == 0 and visited[nx][ny] == False:
                result += 1
                visited[nx][ny] = True
                queue.append((nx, ny))
                exist = True
                break

        if exist == False:
            if data[x + dx[(direction + 2) % 4]][y + dy[(direction + 2) % 4]] == 1:
                return
            else:
                queue.append((x + dx[(direction + 2) % 4], y + dy[(direction + 2) % 4]))


bfs(a,b)

print(result)