자율주행 자동차 (로봇 청소기)

문제 출처 : 코드트리_자율주행 자동차
티어 : 골드5
유형 : 시뮬레이션
출제 : 2017년 상반기 오후 1번
주의사항 : 분기를 나누는 기준을 명확히 할 것.

---

설명이 정말 친절하죠? 혹시 이해를 못할까봐 영상자료까지 준비해주다니요. 실제 시험에서도 그래주면 좋으련만 독해력도 문제의 일부라고 주장을 하니, 백준의 로봇 청소기 문제에 대한 설명을 읽고도 이해할 수 있도록 감을 익히도록 합시다.

---

생각의 흐름

visited 배열을 따로 관리하기보다는 graph의 값을 도로도 인도도 아닌 값으로 바꿈으로서 구분하자고 계획했습니다. 그래프의 바깥이 모두 인도라고 가정되었으므로 범위를 고려하지 않고, 벽의 여부만 체크해도 되겠다고 생각했습니다. 4방향을 순차적으로 탐색하며, 모든 방향이 특정 조건을 만족했을 때 하는 동작(후진)이 있으므로 cnt라는 변수로 탐색횟수를 관리하자고 마음먹었습니다. 마지막으로 탐색한 칸의 숫자를 표시할 answer는 그래프의 0(도로)를 2(지나온 칸)으로 바꿀 때 마다 1씩 추가해줌으로서 표시해주자 생각하고 문제를 풀었습니다.

 

스킬

이번에 설명드릴 스킬은 모듈러 연산입니다. 정육면체 굴리기와 같이 기존까지는 원하는 방향으로 그래프를 움직이기만 하면 되었지만, 이제는 내가 가진 방향을 기준으로 회전을 해야하므로 모든 방향에서 동일하게 작동할 수 있는 코드를 만들 수 있어야 합니다. 그래프의 경우에는 그 핵심이 바로 모듈러 연산인데요, 방향을 가리키는 dx, dy를 시계방향으로 위치하도록 만든 다음 그 인덱스로 조절하는 것이 중요합니다.

 

% 연산에 대해서 알고 계신가요? 파이썬에서 %는 나눗셈을 하고 난 후의 나머지를 반환하는 연산자입니다. 모듈러4 연산을 글로 한번 써볼까요?

0을 4로 나눈 나머지는 0

1을 4로 나눈 나머지는 1

2를 4로 나눈 나머지는 2

3을 4로 나눈 나머지는 3

4를 4로 나눈 나머지는 0

5를 4로 나눈 나머지는 1...

앗! 4부터 나머지가 똑같이 반복되네요!

그렇다면 동쪽을 시작으로 동, 북, 서, 남에 각각 0, 1, 2, 3을 붙여봅시다. 이걸 그림으로 표현해볼까요?

이렇게 나타낼 수 있겠습니다.

 

i를 1씩 키우거나 줄인다라.. 코드로 한번 살펴보겠습니다.

dx = [0, -1, 0, 1]  # 동북서남
dy = [1, 0, -1, 0]
x, y = 원래의 좌표
i = 현재의 방향(0~3 사이)

# 반시계방향으로 회전한 방향
i = (i+1)%4

# 시계방향으로 회전한 방향
i = (i-1)%4  혹은
i = (i+3)%4

 

3을 더하고 4로 나누었을 때의 나머지가, 1을 빼고 4로 나누었을 때의 나머지와 같기 때문에 통상 +3을 씁니다.
회전을 구현하였으니, 위에서 말했던 주의사항을 기억하며 풀이하겠습니다.

 

풀이

def getInput():
    # 입력받는 함수
    global graph
    n, m = map(int, input().split())
    x, y, d = map(int, input().split())
    graph = [list(map(int, input().split())) for _ in range(n)]
    return x, y, d

def move(x, y, d):
    # 자동차를 움직이는 함수
    dx = [0, -1, 0, 1]  # d 기준으로 왼쪽이므로 각각 서 북 동 남
    dy = [-1, 0, 1, 0]

    cnt = 0
    answer = 0
    while True:
        if cnt == 0 and graph[x][y] == 0:
            answer += 1
            graph[x][y] = 2

        nx = x + dx[d]  # 왼쪽 보기
        ny = y + dy[d]

        if graph[nx][ny] == 0:  # 청소 안한 공간 있을 경우
            d = (d+3)%4  # 고개돌려서
            x = nx       # 움직이기
            y = ny
            cnt = 0  #  회전 횟수 초기화

        else:  # 벽이거나 청소 한 공간일 경우
            d = (d+3)%4  # 고개돌리고
            cnt += 1     # 횟수 추가

        if cnt == 4:  # 네 방향 모두 청소 혹은 벽일 경우
            nx = x+dx[(d+3)%4]  # 뒤쪽방향 잡기
            ny = y+dy[(d+3)%4]


            if graph[nx][ny] == 1:  # 뒤가 벽이면 멈추고
                break
            else:  # 아니면 방향 유지하고 뒤로 가기
                x = nx
                y = ny
                cnt = 0
    return answer

# ===== 실제 실행하는 부분 =====
def main():
    x, y, d = getInput()
    print(move(x, y, d))

main()