[Algorithm/BOJ] 14503 : 로봇 청소기.py

문제

 

입력

출력

로봇 청소기가 작동을 시작한 후 작동을 멈출 때까지 청소하는 칸의 개수를 출력한다.

내 풀이

• 로봇 청소기는 N×M 크기의 맵에서 청소를 수행한다.
• 각 칸은 벽(1) 또는 빈 칸(0)으로 구분된다.
• 로봇의 행동 규칙:
  1. 현재 위치를 청소한다.
  2. 왼쪽부터 차례대로 4방향을 탐색하며, 청소하지 않은 칸이 있으면 이동한다.
  3. 4방향 모두 청소가 완료되면 후진을 시도한다.
  4. 후진이 불가능하면 작동을 멈춘다.
• DFS(깊이 우선 탐색)를 사용하면, 재귀적으로 청소와 이동을 구현할 수 있다.

n, m = map(int, input().split())  # 세로, 가로
r, c, d = map(int, input().split())
graph = []
result = 1

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

dx = [0, 1, 0, -1]  # 전진
dy = [-1, 0, 1, 0]
rx = [0, -1, 0, 1]  # 후진
ry = [1, 0, -1, 0]


def rotation(d, i):  # 반시계방향 회전
    return (d + 3 * (i + 1)) % 4


def dfs(graph, start, d):
    y, x = start
    global result
    if graph[y][x] == 0:
        graph[y][x] = 2
        result += 1

    for i in range(4):
        nd = rotation(d, i)  # 반시계 회전
        ny, nx = y + dy[nd], x + dx[nd]  # 전진
        if 0 <= ny < n and 0 <= nx < m and graph[ny][nx] == 0:
            dfs(graph, [ny, nx], nd)
            return

    # 사방에 청소할 곳 없는 경우
    ny, nx = y + ry[d], x + rx[d]  # 기존 방향 유지한 채로 후진
    if 0 <= ny <= n and 0 <= nx <= m and graph[ny][nx] != 1:
        dfs(graph, [ny, nx], d)
    return


graph[r][c] = 2
dfs(graph, [r, c], d)
print(result)