이번 문제는 로봇 청소기의 구동 순서를 구현하고 이를 전체 탐색을 통해 결과 값을 도출하는 문제였다. 그래서 DFS를 이용하여 탐색하기로 하였다. 이 문제에서 어려웠던 점은 방향이 계속 바뀐다는 점이었다. 그래서 우선 dy, dx리스트에 북, 동, 남, 서 순서로 방향을 저장한 후, 현재 바라보는 방향 d에 따라 접근하도록 하였다. 우선 왼쪽을 먼저 보기 때문에 현재 바라보는 방향에서의 왼쪽은 dy, dx에서 (d+3)%4번째 방향이 된다. 이를 통해 4번 반복하며 바라보는 방향의 왼쪽을 탐색하도록 하였고, 만약 청소되어 있거나 벽인 경우에는 왼쪽으로 그냥 돌기만 하도록 하였다. 3번째 조건인 네 방향 청소가 이미 되어 있는 경우에는 뒤쪽 방향에 해당하는 (d+2)%4번째 방향으로 이동하도록 하고, 바라보는 방향 d를 유지한 채로 dfs함수를 재귀호출 하도록 하였다. 이 경우 뒤에가 벽일 경우에는 함수를 종료하도록 하였다.

• n, m을 입력받는다.
• 현재 좌표와 바라보는 방향을 cur리스트에 입력받는다.
• 전체 그래프를 입력받을 리스트 graph를 선언한다.
• n번 반복하며 graph를 입력받는다.
• dy, dx를 북, 동, 남, 서 순서로 선언한다.
• 결과를 저장할 변수 answer를 0으로 선언한다.
• dfs함수를 y, x, d를 인자로 갖도록 하여 선언한다.
  -> answer를 global로 선언한다.
  -> 만약 graph[y][x]가 0일 경우,
  --> answer를 1 증가시킨다.
  --> graph[y][x]를 2로 갱신한다.
  -> 4번 반복하는 for문을 돌린다.
  --> 다음으로 바라볼 방향에 대한 변수 nd를 (d+3)%4로 선언한다. (d에 대한 왼쪽에 해당)
  --> 다음으로 이동할 y, x 좌표에 해당하는 ny, nx를 y+dy[nd], x+dx[nd]로 선언한다.
  --> 만약 graph[ny][nx]가 0일 경우,
  ---> dfs(ny, nx, nd)를 재귀호출한다.
  ---> return 한다.
  --> d를 nd로 갱신한다.
  -> nd를 (d+2)%4로 갱신한다. (d에 대한 뒤쪽 방향)
  -> ny를 y+dy[nd]로 갱신한다.
  -> nx를 x+dx[nd]로 갱신한다.
  -> 만약 graph[ny][nx]가 1일 경우,
  --> return 한다.
  -> dfs(ny, nx, d)를 재귀호출한다.
• dfs(cur[0], cur[1], cur[2])를 호출한다.
• answer를 출력한다.

Code

n, m=map(int, input().split())
cur=list(map(int, input().split()))
graph=[]
for _ in range(n):
    graph.append(list(map(int, input().split())))
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
answer=0
def dfs(y, x, d):
    global answer
    if graph[y][x]==0:
        answer+=1
        graph[y][x]=2
    for _ in range(4):
        nd=(d+3)%4
        ny=y+dy[nd]
        nx=x+dx[nd]
        if graph[ny][nx]==0:
            dfs(ny, nx, nd)
            return
        d=nd
    nd=(d+2)%4
    ny=y+dy[nd]
    nx=x+dx[nd]
    if graph[ny][nx]==1:
        return
    dfs(ny, nx, d)
dfs(cur[0], cur[1], cur[2])
print(answer)