풀이


코딩테스트를 준비하며 예전에 풀어봤던 문제들을 다시 푸는 와중에 발견한 기록하지 못했던 문제이다.

시뮬레이션 구현 문제인데 재귀를 사용하는 형식이다.

재귀를 이해하는데 가장 좋은 문제인 것 같다.

개인적으론 방향전환 설정이 가장 머리 아팠던 것 같다.

시작점에서 부터 clean 함수를 실행하여 좌표 위치가 0 일 경우 청소했다는 표시를 남겨준다.

이후 탐색조건에 맞게 좌측을 탐색하고 청소 가능한 구역일 경우 clean 함수를 호출한다.

네 방향 모두 청소가 불가능한 구역이라면 후진 후 clean 함수를 다시 호출한다.

이때 후진 조차 불가능할 경우 함수를 return 한 후 정답을 출력하면 된다.

소스코드


# 로봇 청소기
import sys
input = sys.stdin.readline
 
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
 
n, m = map(int,input().split())
r, c, d = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
ans = 0
 
def clean(r, c, d):
    global ans
    if graph[r][c] == 0:
        graph[r][c] = 2
        ans += 1
 
    for i in range(4):
        nd = (d+3)%4
        nx = r + dx[nd]
        ny = c + dy[nd]
        if graph[nx][ny] == 0:
            clean(nx, ny, nd)
            return
        d = nd
 
    nd = (d+2)%4
    nx = r + dx[nd]
    ny = c + dy[nd]
    if graph[nx][ny] == 1:
        return
    clean(nx, ny, d)
 
clean(r, c, d)
print(ans)

References