백준 14503 파이썬

문제

이 문제는 먼저 무조건적인 DFS나 BFS가아닌 여기에 특정 조건이 추가되었다.
먼저 로봇청소기가 1번이상 회전을 하고 회전했을때 앞의 방향이 청소를 하지 않고
벽이 아니라면 방문해주는 식으로

또한
회전을 4번이나 했을 때는 다른 탐색처럼 종료를 하는것이아니라 현재 방향에서 반대 방향
쪽으로 후진을한다.
이 모든점을 고려하여 코드에 녹인결과는 이렇다.

#입력
# 첫째 줄에 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 50)

# 둘째 줄에 로봇 청소기가 있는 칸의 좌표 (r, c)와 바라보는 방향 d가 주어진다. d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽을 바라보고 있는 것이다.

# 셋째 줄부터 N개의 줄에 장소의 상태가 북쪽부터 남쪽 순서대로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 빈 칸은 0, 벽은 1로 주어진다. 지도의 첫 행, 마지막 행, 첫 열, 마지막 열에 있는 모든 칸은 벽이다.

# 로봇 청소기가 있는 칸의 상태는 항상 빈 칸이다.

import sys
from collections import deque


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

N, M = map(int, sys.stdin.readline().split())

y, x, d = map(int, sys.stdin.readline().split())

matrix = [[] * M for _ in range(N)]
visit = [[0] * M for _ in range(N)]
#matrix 정보 입력
for i in range(N):
  matrix[i] = list(map(int, sys.stdin.readline().split()))


count = 1
Q = deque()
Q.append([y, x, d])
visit[y][x] = 1
#BFS탐색을 통해 로봇청소기가 청소하는 구역의 개수를 count에 저장
while Q:
  curY, curX, curD = Q.popleft()

  #회전만 하고 방문을 안했다면 flag는 0으로
  flag = 0
  turn_count = 0
  for i in range(4):
    curD -= 1
    
    if(curD < 0):
      curD = 3
    newY = curY + dy[curD]
    newX = curX + dx[curD]

    if(newY >= 0 and newY < N and newX >= 0 and newX < M):
      if(matrix[newY][newX] == 0 and visit[newY][newX] == 0):
        visit[newY][newX] = 1
        #print('(', newY, ', ', newX, ') 방문!')
        Q.append([newY, newX, curD])
        count += 1
        flag = 1
        break;

  if(flag == 0):
    #지금 보고있는 방향의 반대방향
    back = (curD + 2) % 4
    newY = curY + dy[back]
    newX = curX + dx[back]
    
    if(newY >= 0 and newY < N and newX >= 0 and newX < M):
      if(matrix[newY][newX] == 0):
        Q.append([newY, newX, curD])
    
print(count)    
    

DFS BFS문제들을 많이 풀어보니 어디서 본듯한 문제같은 느낌이 낫고
이에따라 큰 시행착오없이 문제를 해결해갔다. BFS의 이해도와 구현을
조금만 할 줄 안다면 풀 수있는 수준인 것같다.
또한 이런문제는 문제에대한 확실한 이해가 필요하다.
보통 문제처럼 벽이아닌 위치를 모두 탐색해보는 것이아닌 방문했던 위치도 방문하고
회전을 한다는 특정 조건을 구현해야해서 문제를 확실히 읽어야 했던 문제이다.