[BOJ/python] 14503번 로봇 청소기

https://www.acmicpc.net/problem/14503

14503번: 로봇 청소기

 

문제 해석

 

N * M 크기의 방이 존재한다. 이 방의 가장자리는 모두 벽으로 이루어져 있고, 추가적인 벽이 존재 할 수 있다.

벽은 1, 빈 공간은 0으로 입력된다.

 

로봇 청소기는 다음과 같은 규칙을 통해 동작한다.

1. 현재 위치를 청소한다.

2.

a. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향이 청소하지 않은 공간이라면 회전하고, 전진한 후 1번부터 진행한다.

b. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향이 청소한 공간이라면 회전 한 후 2번으로 돌아간다.

c. 상하좌우 모두 탐색 하였는데 청소 할 공간이 없다면 현재 방향에서 1칸 후진한다. 

d. 상하좌우 모두 탐색 하였는데 청소 할 공간이 없고 후진 할 공간이 벽이면 종료한다.

 

입력으로는 로봇 청소기의 위치 r, c 와 바라보는 방향 d 가 주어지며 0부터 차례대로 북, 동, 남, 서 이다.

출력으로는 로봇 청소기가 청소한 모든 칸을 출력한다.

---

코드

input = __import__('sys').stdin.readline
n, m = map(int, input().split())
r, c, di = map(int, input().split()) # 좌표, 보는 방향
direction = [(-1,0),(0,1),(1,0),(0,-1)] # 북 동 남 서
arr = []
for i in range(n):
    arr.append(list(map(int, input().split())))

ans = 0
while 1:
    # 현재 위치 청소하기
    if arr[r][c] != 2:
        ans += 1
    arr[r][c] = 2

    # 현재 위치에서 탐색
    flag = False # 청소할 공간이 있으면 True
    for i in range(4):
        dx, dy = direction[(di + i) % 4]
        if arr[r + dx][c + dy] == 0:
            flag = True
    
    # 청소할 공간이 있을 때
    if flag:
        di += 3 # 왼쪽으로 돔
        dx, dy = direction[di % 4]
        # 왼쪽이 청소 할 수 있을 때
        if arr[r+dx][c+dy] == 0:
            r += dx
            c += dy
        # 없을 때

    # 청소할 공간이 없을 때
    else:
        dx, dy = direction[(di + 2) % 4]
        # 후진 위치가 벽인지 확인
        if arr[r+dx][c+dy] == 1: # 벽이면 종료
            print(ans)
            exit()
        else:
            r += dx
            c += dy

---

문제 풀이

 

먼저 주어진 조건에 대한 알고리즘을 생각해 보았다.

2번 규칙에서 청소가 가능한  a, b를 나누고 청소가 불가능한 c, d를 나누어 풀 생각을 하였다.

a, b 를 만족하는 조건은 상하좌우에 청소 할 공간이 있을 때 이고

c, d 를 만족하는 조건은 청소 할 공간이 없을 때 이다.

이를 판별하기 위해 다음과 같은 코드를 작성했다.

# 현재 위치에서 탐색
    flag = False # 청소할 공간이 있으면 True
    for i in range(4):
        dx, dy = direction[(di + i) % 4]
        if arr[r + dx][c + dy] == 0:
            flag = True

 다음은 flag == True 일 때 a, b 조건에 맞춰 코드를 그대로 작성했다.

a, b 조건 모두 항상 왼쪽 방향을 바꿔주고

a 조건에 해당할 때만 1칸 전진하도록 해주었다.

 

c, d 조건에서는 후진 방향이 벽인지 확인하고 벽이라면 프로그램 종료, 아니라면 후진하여 다음 으로 진행하도록 하였다.

 

거의 처음으로 시뮬레이션 알고리즘 부분에서 짠 코드가 깔끔하게 짜여진 것 같다.

항상 여러가지 오류가 있어 애먹었는데 이번 문제는 처음 동서남북 방향 설정 실수를 제외하고는 완벽하게 짠 것 같다.

 

원문

https://ddingmin00.tistory.com/26

[BOJ/python] 14503번 1로 만들기