[백준 14503번] 파이썬 - 로봇 청소기

백준 14503_로봇 청소기

시간제한 2초, 메모리제한 2MB

# 조건

• 로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.
• 로봇 청소기가 있는 방은 N x M 크기의 직사각형으로 나타낼 수 있으며, 1×1 크기의 정사각형 칸으로 나누어져 있다.
• 각각의 칸은 벽 또는 빈 칸이다.
  • 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다.
  • 방의 각 칸은 좌표 (r,c)로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가 (0,0), 가장 남쪽 줄의 가장 동쪽 칸의 좌표가 (N-1, M-1)이다.
  • 즉, 좌표 (r,c)는 북쪽에서 (r+1)번째에 있는 줄의 서쪽에서 (c+1)번째 칸을 가리킨다.
  • 처음에 빈 칸은 전부 청소되지 않은 상태이다.
• 로봇 청소기는 다음과 같이 작동한다.

1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
   1. 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
   2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
   1. 반시계 방향으로 90∘ 회전한다.
   2. 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
   3. 1번으로 돌아간다.

입력

• 첫 줄에 방의 크기 N, M ( 3<= N, M <=50)
• 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 (r,c)와 처음에 로봇 청소기가 바라보는 방향 d가 입력
• d가 0인 경우 북쪽, 1인 경우 동쪽, 2인 경우 남쪽, 3인 경우 서쪽
• 셋째 줄부터 N개의 줄에 각 장소의 상태를 나타내는 N x M 개의 값이 한 줄에 M개씩 입력된다.
• i번째 줄의 j번째 값은 칸 (i, j)의 상태를 나타내며, 이 값이 0인 경우 (i, j)가 청소되지 않은 빈 칸이고, 1인 경우 (i, j)에 벽이 있는 것
• 방의 가장 북, 남, 서, 동쪽 줄 중 하나 이상에 위치한 모든 칸에는 벽이 있다.
• 로봇 청소기가 있는 칸은 항상 빈 칸

출력

• 로봇 청소기가 작동을 시작한 후 작동을 멈출 때까지 청소하는 칸의 개수를 출력한다.

# 접근 방법

• bfs를 이용하여 구현하는 문제이다.
• 청소기가 반시계로 돌기 때문에 0 3 2 1 순서로 탐색해준다.
  • 이 때 -> d=(d+3)%4 를 이용하여 0 3 2 1 0 3 2 와 같이 회전할 수 있도록 해준다.
• visited 배열을 만들어주어, 방문 표시를 남긴다 -> 더불어 청소를 하였다는 증거
• 현재 칸의 4칸 중 청소해야되는 칸이 없다면, 후진이 가능한지 확인
  • 가능하다면, q에 넣어주고 1번으로 돌아간다.
• 청소되지 않은 빈 칸이 있는 경우,
  • visited에 표시해주고 현재 좌표를 변경해준다.
  • 이 때, 한 방향에 대해서 진행해야 되므로
  • 4방향에 대해 모두 탐색을 한 후, 전진과 후진을 결정해야 한다. -> flag 변수를 통해 청소를 했다면 true로 변경해준다.

## 북, 동, 하, 서 ( 시계방향 )dr = [-1, 0, 1, 0]  
dc = [0, 1, 0, -1]  

n, m = map(int, input().split())  
r, c, d = map(int, input().split())  
arr = [list(map(int, input().split())) for _ in range(n)]  
## 방문 쳌  
visited = [[0]*m for _ in range(n)]  

## 시작지 방문쳌 and 카운트!  
visited[r][c] = 1  
cnt = 1  

while True:  
    flag = 0            ## 아직 아무것도 청소 안했음!  
    for _ in range(4):  ## 4방향을 돈다!  
        d = (d+3) % 4   ## 왼쪽방향으로 한 칸 돌린다! 중요!!!!!1  
        nr = r + dr[d]  
        nc = c + dc[d]  

        ## 범위 안에 들고, 빈 칸이고, 청소할 수 있다면!  
        ## 들려서 청소하고, 카운트하고, 현재 위치를 갱신하고, flag 변경!  
        if 0 <= nr < n and 0 <= nc < m and arr[nr][nc] == 0:  
            if visited[nr][nc] == 0:  
                visited[nr][nc] = 1  
                cnt += 1  
                r = nr  
                c = nc  
                flag = 1        ## 청소 했다는 뜻  
                break  

    if flag == 0:               ## 위의 for문에 들어가지 못했을 때  
        ## 즉 네 방향 모두 청소를 할 수 없을 때  
        ## 후진 했을 때 벽이면 break        ## 만약 뒤가 벽이 아니라면! 그 위치를 다시 갱신!!!  
        if arr[r-dr[d]][c-dc[d]] == 1:  
            print(cnt)  
            break  
        else:  
            r, c = r-dr[d], c-dc[d]