풀이
코딩테스트를 준비하며 예전에 풀어봤던 문제들을 다시 푸는 와중에 발견한 기록하지 못했던 문제이다.
시뮬레이션 구현 문제인데 재귀를 사용하는 형식이다.
재귀를 이해하는데 가장 좋은 문제인 것 같다.
개인적으론 방향전환 설정이 가장 머리 아팠던 것 같다.
시작점에서 부터 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)