로봇 청소기 [백준 14503] - python

from collections import deque
import sys
input = sys.stdin.readline

def BOJ14503() :
  global N, M
  global directions
  global cleared
  global graph

  def bfs(r, c, d) :
    queue = deque()
    queue.append([r, c, d])
    
    while queue :
      x, y, direction = queue.popleft()
      flag = True
      for dir_x, dir_y, dir in directions[direction] :
        n_x = x + dir_x
        n_y = y + dir_y
        n_dir = dir
        if 0 <= n_x < N and 0 <= n_y < M and cleared[n_x][n_y] == 0 and graph[n_x][n_y] == 0:
          cleared[n_x][n_y] = 1
          queue.append([n_x, n_y, n_dir])
          flag = False
          break
      
      if flag :
        back_x, back_y, _ = directions[direction][1]
        n_x = back_x + x
        n_y = back_y + y
        if graph[n_x][n_y] != 1 :
          queue.append([x + back_x, y + back_y, direction])
  
  N, M = map(int, input().split())
  r, c, d = map(int, input().split())
  
  directions = {
    0: [[0, -1, 3], [1, 0, 2], [0, 1, 1], [-1, 0, 0]], 
    1: [[-1, 0, 0], [0, -1, 3], [1, 0, 2], [0, 1, 1]],
    2: [[0, 1, 1], [-1, 0, 0], [0, -1, 3], [1, 0, 2]], 
    3: [[1, 0, 2], [0, 1, 1], [-1, 0, 0], [0, -1, 3]]
  }

  graph = []
  cleared = [[0 for _ in range(M)] for _ in range(N)]
  for _ in range(N) :
    graph.append(list(map(int, input().split())))

  cleared[r][c] = 1
  bfs(r, c, d)
  
  count = 0
  for i in range(N - 1) :
    for j in range(M - 1) :
      if cleared[i][j] == 1 :
        count += 1
  print(count)

BOJ14503()

 

접근 방법 :

1. 각 방향에서 왼쪽으로의 회전을 했을때에 대한 [이후의 왼쪽 회전에 대한 정보, 바라보게 될 방향]을 변수로 가지고 있으면 좋겠다고 생각을 한 후에 변수를 정의해 주었다.

2. bfs를 이용하여 청소기가 탐색하는 로직을 구현해주고자 하였다.

3. flag를 이용해 현재 청소기가 있는 위치에서 더이상 탐색할수 없음을 표현해 주었고 for문을 탈출

4. 어디로든 갈수 없는 상태로면 후진 동작을 코드로 구현해주었다.

 

 

 

 

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

14503번: 로봇 청소기