[Codetree] 자율주행 자동차 (Python 파이썬)

자율주행 자동차

Simulation

---

n * m 크기의 도로에 1 * 1 크기의 자율주행 자동차가 주어집니다.

자율주행 자동차는 다음 규칙에 따라서 움직입니다.

1. 현재 방향을 기준으로 왼쪽 방향으로 한 번도 간 적이 없다면 좌회전해서 해당 방향으로 1 칸 전진합니다.

1. 만약 왼쪽 방향이 인도거나 이미 방문한 도로인 경우 좌회전하고 다시 1번 과정을 시도합니다.

1. 2번에 대해 4방향 모두 확인하였으나 전진하지 못한 경우에는 바라보는 방향을 유지한 채로 한 칸 후진을 하고 다시 1번 과정을 시도합니다.

4. 3번 과정을 시도하려 했지만 뒷 공간이 인도여서 후진조차 하지 못한다면 작동을 멈춥니다.

자율주행 자동차가 작동을 멈췄을 때 거쳐갔던 도로의 총 면적을 구하는 프로그램을 작성하세요. 처음 위치의 도로도 총 면적에 함께 계산합니다.

입력 형식

첫째 줄에 도로의 세로 크기 n과 가로 크기 m이 주어집니다.

둘째 줄에 자율주행 자동차의 초기 위치 (x, y)와 바라보는 방향 d가 주어집니다. d는 0부터 3까지 숫자로 주어지고, 순서대로 북쪽, 동쪽, 남쪽, 서쪽을 의미합니다. 자동차의 처음 위치 x는 위쪽에서부터 아래쪽까지 0부터 n-1까지 차례대로 번호를 매겨 구분하며, y는 왼쪽에서 오른쪽까지 차례대로 번호를 매겨 구분합니다.

셋째줄부터 n+2번째 줄까지는 도로의 상태가 주어집니다. 도로는 0, 인도는 1으로 주어집니다.

• 3 ≤ n, m ≤ 50
• 자율주행 자동차가 있는 칸은 도로일 것이라 가정해도 좋습니다.
• 격자의 첫번째 행과 마지막 행, 첫번째 열과 마지막 열은 항상 인도일 것이라고 가정해도 좋습니다.

출력 형식

초기 상태의 방문 면적을 1으로 가정하고, 자율주행 자동차가 방문했던 도로의 총 면적을 구합니다.

 

제한

시간 제한: 1000ms
메모리 제한: 80MB

---

풀이

문제 조건에 맞게 변수를 세팅해 준다. 주어진 조건에 따라 인덱스로 이동방향에 접근할 수 있도록 dx, dy를 선언한다.

 

이동이 진행될 때 마다 현재 방향 기준으로 반시계방향으로 4번 탐색을 한다. 도중에 이동 가능한 도로를 발견하면 이동하고, 발견하지 못한 경우 뒤로 이동한다. 이 과정을 반복하다 뒤로 이동할 수 없는 경우 자율주행을 멈추게 된다.

 

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

dx = [-1,0,1,0]
dy = [0,1,0,-1]
n, m = map(int, input().split())
x, y, d = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
cnt = 1
board[x][y] = 2

def solve(n,m,x,y,d,flag=0):
    global cnt
    if flag == 4:
        move_d = (d+2)%4
        nx, ny = x+dx[move_d], y+dy[move_d]
        if board[nx][ny] == 1:
            return
        else:
            board[nx][ny] = 2
            solve(n,m,nx,ny,d,0)
    else:
        move_d = (d+3)%4
        nx, ny = x+dx[move_d], y+dy[move_d]
        if board[nx][ny] == 0:
            board[nx][ny] = 2
            cnt += 1
            solve(n,m,nx,ny,move_d,0)
        else:
            solve(n,m,x,y,move_d,flag+1)


solve(n, m, x, y, d, 0)
print(cnt)

board에서 0은 이동 가능한 도로, 1은 이동 불가 지역, 2는 이미 방문했던 도로를 나타낸다. flag를 통해 현재 위치에서의 탐색 횟수를 저장하고 4번의 탐색이 끝났다면 바라보는 방향을 유지한 채 뒤로 이동한다. 

바라보는 방향의 변경은 왼쪽으로 도는 것은 (d+3)%4, 뒤로 도는 것은 (d+2)%4로 나타낼 수 있다.

 

https://www.codetree.ai/training-field/frequent-problems/autonomous-driving/description?page=1&pageSize=20&username=thkyang324