[Baekjoon] 백준 14503 로봇 청소기 Python

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

 

❗풀이 방법

1. 현재 위치 청소
2. 현재 좌표 기준 4방향 확인
   • 반시계 방향이므로 왼쪽 회전
   • 다음 위치가 청소가 안 되어 있다면 clean함수 실행
   • 바로 return -> 다른 방향도 순차적으로 확인할 것이 아니라 다음 좌표가 정해지면 다시 그 좌표를 기준으로 청소하는 것이기 때문
3. 4방향에 전부 청소가 다 되어 있다면 후진
   • 현재 좌표 이동거리만큼 빼기
   • 후진 좌표로 이동할 수 있다면 다시 clean함수 실행
   • 없다면 return 으로 이동 멈춤

 

❗코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split(" "))

graph = []

start_x, start_y, d = map(int, input().split(" "))

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

result = 0


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

# 0: 청소 안 됨
# 1: 벽
# 2: 청소함


def clean(x, y, d):
    global result


    if graph[x][y] == 0:
        graph[x][y] = 2
        result += 1

    # 4방향을 기준으로 현재 가진 방향을 갖고 재귀
    for i in range(4):
        d = (d+3)%4
        nx = x + dx[d]
        ny = y + dy[d]

        if 0<=nx and nx<n and 0<= ny and ny <m and graph[nx][ny] == 0:
            clean(nx, ny, d)
            return # 한 방향에서 재귀가 시작했으므로 다음 방향에서 실행되지 않도록 막는 것

	# 후진하는 경우
    bx = x - dx[d]
    by = y - dy[d]

    if 0 <= bx and bx < n and 0 <= by and by < m and graph[bx][by] != 1:
        clean(bx, by, d)
    else:
        # 후진이 불가한 경우
        return


clean(start_x, start_y, d)
print(result)