[백준 시뮬레이션 문제 14503] 로봇 청소기

## 백준 온라인 저지 시뮬레이션 문제 14503번 - 로봇 청소기

#난이도 : 중

N, M = map(int,input().split())

r, c, d = map(int,input().split())

room = []
for i in range(N): #전체 맵
  room.append(list(map(int,input().split())))

mark_map = [] #이미 청소한곳을 마크하는 맵
for i in range(N):
  mark_map.append([0]*M)

direction_li = [0,1,2,3] #북, 동, 남, 서 순
dx = [0,1,0,-1]
dy = [-1,0,1,0]

pos_x = c
pos_y = r
mark_map[pos_y][pos_x] = 1
tol = 0
count = 1
d = (d-1) % 4 #반시계방향부터 탐색

while room[pos_y][pos_x] != 1 : #이동한곳이 벽이면 중지
  if room[pos_y + dy[d]][pos_x+dx[d]] == 0 :
    if mark_map[pos_y + dy[d]][pos_x+dx[d]] == 0: #벽이 아니고 청소한곳이 아니면 직진 (유일한 직진 조건)
      pos_x += dx[d]
      pos_y += dy[d]
      mark_map[pos_y][pos_x] = 1
      tol = 0
      count += 1
      d = (d-1) % 4 #이동하고나서 미리 반시계방향 회전 (바로 탐색할수있도록)
      tol += 1
    else: #벽은 아니지만 청소를 이미 한 곳이라면...
      if tol == 4 :
        pos_x -= dx[d]
        pos_y -= dy[d]
        tol = 0
        d = (d-1) % 4 #이동하고나서 미리 반시계방향 회전 (바로 탐색할수있도록)
        tol += 1
        
      else: 
        d = (d - 1) % 4 
        tol += 1

  else: #이동하려고 하는 곳이 벽이라면...
    if tol == 4:
      pos_x -= dx[d]
      pos_y -= dy[d]
      tol = 0
      d = (d-1) % 4 #이동하고나서 미리 반시계방향 회전 (바로 탐색할수있도록)
      tol += 1
      
    else:
      d = (d-1) % 4 
      tol += 1
    
print(count)

 

#시간복잡도 : O(NM)