백준 14503 in Python 파이썬 풀이

유형 : 구현 

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

14503번: 로봇 청소기

 

이 문제에서 어렵다고 느껴졌던 점은 바라보는 '방향'도 고려해서 새로운 좌표로 이동시키는 것이었다. 

 현재 바라보는 방향을 t라고 이름붙이겠다.

옆의 그림과 같이, 문제에서 북-동-남-서 순서대로 바라보는 방향을 지정했다.

그리고 북쪽을 바라보는 상황에서 앞으로 한칸 전진하면 서쪽, 동쪽을 바라보는 상황에서 앞으로 한칸 전진하면 북쪽, 남쪽을 바라보는 상황에서 앞으로 한칸 전진하면 동쪽, 서쪽을 바라볼 때 한칸 전진하면 남쪽이 되는 상황이다.이를 수식으로 표현하면

(t+3)%4 이다. 동서남북 4가지의 경우가 있으므로 4로 나눈 나머지를 이용하고, t+3를 해주면 들어맞는다.

 

우리는 뒤로 이동해야 하는 경우도 알아내야 한다. 현재위치에서 사방이 벽인 경우, 뒤로 한칸 이동시키도록 해야하기 때문이다.

뒤로 이동하는 경우는 (t+2)%4 이다. 

 

# 14503  로봇 청소기

dx = [-1,0,1,0] # 북동남서로 고치기 !
dy = [0,1,0,-1]

n, m = map(int, input().split())
x, y, t = map(int, input().split())
array = [] # 칸
count = 0

for i in range(n):
    array.append(list(map(int, input().split())))

def clean(x, y, t):
    global count
    if array[x][y] == 0:
        array[x][y] = 2 # is visited
        count += 1
    for i in range(4):
        nt = (t + 3)%4 # 이게 어느정도 핵심이다 ! 현재 바라보고 있는 방향에서 좌측 회전을 한 후 새로운 t
        nx = x + dx[nt]
        ny = y + dy[nt]
        if array[nx][ny] == 0:
            clean(nx, ny, nt)
            return
        t = nt # t는 보존하려고 다시 둔다
    nt = (t+2) % 4 # 뒤로 이동을 위해 사용 !
    nx = x + dx[nt]
    ny = y + dy[nt]
    if array[nx][ny] == 1:
        return
    clean(nx, ny, t) # 뒷칸이 벽이 아닌 경우에 바라보는 방향 그대로 뒤로 한칸 이동시키기


clean(x,y,t)

print(count)

간혹가다가 구현문제에서 2차원 배열상에서 이동하는 문제가 많이 나오니까 상하좌우 이동하는 방법과 방향이 주어지는 경우를 대비해 잘 숙지해야 할 것 같다 !