14503_로봇청소기

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

14503번: 로봇 청소기

 

기본적으론 재귀함수의 형태를 띠지만 무작정 dfs로 구현하기에는 조금 무리가 있다.

 

1. 현재 위치를 청소한다.
2. 현재 위치에서 다음을 반복하면서 인접한 칸을 탐색한다.
   1. 현재 위치의 바로 왼쪽에 아직 청소하지 않은 빈 공간이 존재한다면, 왼쪽 방향으로 회전한 다음 한 칸을 전진하고 1번으로 돌아간다. 그렇지 않을 경우, 왼쪽 방향으로 회전한다. 이때, 왼쪽은 현재 바라보는 방향을 기준으로 한다.
   2. 1번으로 돌아가거나 후진하지 않고 2a번 단계가 연속으로 네 번 실행되었을 경우, 바로 뒤쪽이 벽이라면 작동을 멈춘다. 그렇지 않다면 한 칸 후진한다.

 

되게 상세하게 설명이 나와있는데 이 그대로만 구현하면 된다. 꼼꼼하게 구현해주는게 포인트

 

청소하지 않은 빈공간이 있을경우에만 청소를 해주고,

회전한다음에 전진을 해야한다. 

 

이런 세세한 부분을 맞춰야 한다.또한 dfs처럼 4바퀴를 돌았을때 이전 탐색했던 방향으로 돌아가는 것이 아닌, 후진을 해야한다. 후진을 한다는 의미는 결국 진행방향은 그대로 두고 몸만 뒤로 가는것을 의미한다.

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
r,c,d = map(int,input().split())
board = [ list(map(int,input().split())) for _ in range(n) ]

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

cnt = 0
def dfs(x,y,d):
    global cnt
    if not board[x][y]:
        board[x][y] =2
        cnt +=1

    for i in range(4):
        d = (d-1) % 4
        nx,ny = x + dx[d], y + dy[d]

        if 0<=nx<n and 0<=ny<m and not board[nx][ny]:
            dfs(nx,ny,d)
            break
    else:
        d = (d-2)%4
        nx,ny = x + dx[d],y+dy[d]
        if board[nx][ny] ==1:
            return
        else:
            dfs(nx,ny,(d-2)%4)

dfs(r,c,d)
print(cnt)