14503 로봇 청소기

14503 로봇 청소기 - 백준

• 문제 한줄 정리
  - 현재 위치를 청소하고, 현재 위치에서 왼쪽방향부터 차례대로 탐색을 진행하며 청소할 공간이 존재한다면 그 방향으로 회전하고 이동한다.
  • 네 방향이 모두 청소 되어 있거나, 벽이 존재한다면 뒤로 후진한다.
  • 벽이라 후진할 수 없는 경우 동작을 멈춘다.
  • 이 때, 로봇 청소기가 청소할 수 있는 칸의 개수를 출력하라.
• Basic Idea
  - 현재 로봇이 보고 있는 방향에 따라, 이동 시(왼쪽이나 뒤) 변하는 좌표의 위치가 달라진다. 예를 들어 로봇이 북쪽으로 향하고 있을 때는 뒤로 이동할 때 y좌표가 1만큼 증가하지만, 로봇이 남쪽으로 향하고 있을 때는 뒤로 이동할 때 y좌포가 1만큼 감소한다.
• What To Do?
  - input을 받는다
  • 현재 위치가 청소되어 있지 않다면, 현재 위치를 청소한다.
  • 왼쪽 방향으로 차례대로 4곳을 탐색하며, 만약 청소할 곳(=0)이 존재한다면 청소를 하고 청소할 곳이 존재하지 않는다면(벽=1 / 이미 청소한 곳=2) 뒤로 간다.
  • 만약 뒤로 갈 곳이 존재하지 않는다면 로봇이 청소한 곳의 수를 출력한다.
• Algorithm Analysis
  - N : 맵의 세로 크기, M : 맵의 가로 크기
  • Time Complexity : T(N, M) = θ(N×M)
  • Space Complexity : θ(N×M)
• Full Code
  - ssuda0/BaekJoon/14503.cpp