[CT] 자율주행 자동차

1. 문제

• 도로 : n * m

• 자동차 : 1 * 1

• 다음 규칙에 따라서 이동

  1. 현재 방향을 기준으로 왼쪽으로 간 적이 없으면 좌회전 + 1칸 전진

     

  2. 왼쪽이 인도/이미 방문한 경우 좌회전 + 1번 과정 시도

     

  3. 2번에 대해 4방향 모두 확인해도 전진 불가하다면

     1. 현재 방향 유지한 채로 1칸 후진 + 1번 과정

        

     2. 후진을 못하는 상황이면 작동 stop

        
  • 입력
    • 도로의 세로 크기 n, 가로 크기 m
    • 자율주행 자동차의 초기 위치 (x, y)와 바라보는 방향 d
      • d : 0부터 3까지 숫자로 주어지고, 순서대로 북쪽, 동쪽, 남쪽, 서쪽
      • x : 위쪽에서부터 아래쪽까지 0부터 n-1까지 차례대로 번호
      • y : 왼쪽에서 오른쪽까지 차례대로 번호
    • 셋째줄부터 n+2번째 줄까지는 도로의 상태가 주어집니다. 도로는 0, 인도는 1으로 주어집니다.
    • 3 ≤ n, m ≤ 50
    • 자율주행 자동차가 있는 칸은 도로일 것이라 가정해도 좋습니다.
    • 격자의 첫번째 행과 마지막 행, 첫번째 열과 마지막 열은 항상 인도일 것이라고 가정해도 좋습니다.

⇒ 자율주행 자동차가 작동을 멈췄을 때 거쳐갔던 도로의 총 면적? (처음 위치의 도로 포함)

2. 풀이

• simulation
• while 반복문 내에서 좌회전 가능 여부 후 이동 및 후진 진행
• 좌회전 시 방향은 N(0) → W(3), W(3) → S(2), S(2) → E(1), E(1) → W(0) 이므로, 좌회전 후 방향은 d = (d + 3) % 4 와 같다

3. 코드

n, m = map(int, input().split()) #  n = height, m = width
x, y, d = map(int, input().split())                             # d = 0 ~ 3 : N E S W
roads = [ list(map(int, input().split())) for _ in range(n)]    # 0 : road, 1: sidewalk
visited = [[0]*m for _ in range(n)]

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

def can_move(x, y):
    move = False 
    if  0 <= x < n and 0 <= y < m and roads[x][y] == 0 and not visited[x][y]:
        move = True
    return move

visited[x][y] = 1
trial = 0
while True:
    d = (d + 3) % 4
    nx = x + dx[d]
    ny = y + dy[d]
    trial += 1
    
    if can_move(nx, ny): # if can move, (in range, is a road, not visited),  move (change x, y, reset trial, change visited)#  
        x, y = nx, ny
        trial = 0
        visited[x][y] = 1
        
    else:   # if can't move, (already visited, out of range)
        if trial == 4 :     #   if trial == 4 
            nx = x - dx[d]
            ny = y - dy[d]            
            if 0 <= nx < n and 0 <= ny < m and roads[nx][ny] == 0:  #if can go backwards, go backwards(change x, y, reset trial)
                x = nx
                y = ny
                visited[x][y] = 1
                trial = 0                
            else:       # if can't move backwards, (already visited, out of range)
                break
    
        else:       # if trial <4 
            continue

answer = 0
for i in range(n):
    for j in range(m):
        answer += visited[i][j]
print(answer)

+α