백준 14503: 로봇 청소기

아이디어

2차원 리스트로 청소 공간 표현: space[row][col]

0: 청소 안된 빈 칸, 1: 벽. 추가로 2: 청소 된 칸 체크용도

방향 벡터로 이동을 표현

drow = [-1, 0, 1, 0], dcol = [0, 1, 0 -1]

북, 동, 남, 서 순으로 정함. 이렇게 하면 drow[d] = 전진, -drow[d] = 후진으로 표현 가능!

나머지 연산으로 회전을 표현

90도 시계 방향 회전: 0 → 1 → 2 → 3 → 1 → 2 → …

90도 반시계 방향 회전: 0 → 3 → 2 → 1 → 0 → 3 → …

-1 mod 4 = 3이므로 d = (d - 1) % 4로 구현 가능!

while 문으로 반복: 작동 멈출 때까지 계속 반복한다.

for문으로 4방향 탐색, 0을 찾았으면 for 문 탈출

찾았으면 for문 탈출하고 find = True 기록해서 다음 코드가 실행되지 않도록 한다.

0을 못찾았으면 후진 시도, 후진 못하면 종료. 후진 못하면 while문 탈출.

범위 체크

0 ≤ row < n, 0 ≤ col < m을 체크하지 않아도 정상적으로 작동. 가장자리에는 벽이 있기 때문

시간 복잡도

O(4nm) = O(nm). n, m의 최대가 50이므로 50*50 = 2500 < 1억이므로 가능!

코드 구현

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
row, col, drt = map(int, input().split())
space = [list(map(int, input().split())) for _ in range(n)]

drow = [-1, 0, 1, 0]
dcol = [0, 1, 0, -1]

cnt = 0
while True:
    find = False

    if space[row][col] == 0:
        space[row][col] = 2
        cnt += 1
    
    for i in range(4):
        if space[row + drow[i]][col + dcol[i]] == 0:
            find = True
            drt = (drt - 1) % 4
            if space[row + drow[drt]][col + dcol[drt]] == 0:
                row += drow[drt]
                col += dcol[drt]
                break
    
    if find == False:
        if space[row - drow[drt]][col - dcol[drt]] != 1:
            row -= drow[drt]
            col -= dcol[drt]
        else:
            break

print(cnt)