14503-로봇청소기

www.acmicpc.net/problem/14503

1. 처음 로봇이 주어진 방향에 인덱스를 맞춰서 dx, dy 를 설정

2. 네 방향이 벽이거나 청소한 곳이면 후진해가며 아닐때까지 탐색

3. 뒤가 벽이면 exit()

4. 뒤가 벽이 아니면 후진

5. 4 방향을 순서대로 탐색하며 청소하지 않은 곳을 청소해주고 해당 위치로 dfs 재귀

n, m = map(int,input().split())
x, y, dir = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(n)]
total = 0
# 상 우 하 좌
# !!! dir 은 -1 해가면서 회전
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]


def robot(x, y, dir):
    global total
    # 네방향이 벽이거나 청소한 곳인 이상 계속 후진
    while a[x - 1][y] and a[x + 1][y] and a[x][y + 1] and a[x][y - 1]:
        # 뒤로가는 ndir과 뒤의 nx,ny 설정
        ndir = (dir - 2) % 4
        nx = x + dx[ndir]
        ny = y + dy[ndir]
        # 뒤가 벽이라면
        if a[nx][ny] == 1:
            print(total)
            exit()
        # 뒤가 벽이 아니라면 후진, dir 은 그대로
        x, y = nx, ny

    # 네방향 탐색
    for i in range(1,5):
        index = dir - i
        ndir = index % 4
        nx = x + dx[ndir]
        ny = y + dy[ndir]
        if not a[nx][ny]:
            a[nx][ny] = 2
            total += 1
            robot(nx, ny, ndir)


a[x][y] = 2
total += 1
robot(x,y,dir)