[BOJ/백준] 14503 로봇 청소기

# 14503 로봇 청소기

# r,c 는 r은 북쪽(X) c는 서쪽(Y)
# 동서남북
# sudo
# 1. 현재위치 청소
# 2. 현재 위치에서 왼쪽으로 회전 + 전진 -> 청소 반복
#  없으면 그 방향으로 계속 회전
# 4방향 전부 청소 완료하면 한칸 후진
# 후진이 안되면 멈춤
# d 0,1,2,3 북동남서
# 빈칸은 0, 벽은 1
N,M = map(int,input().split())
robotX,robotY,direction = map(int,input().split())

arr = [list(map(int,input().split())) for _ in range(N)]
rotate = [3,0,1,2]
visited = [[True] *M for _ in range(N)]
cnt = 1
stack = [(robotX,robotY,direction)]
dx = [-1,0,1,0]
dy = [0,1,0,-1]
visited[robotX][robotY] = False
while stack:
    x,y,cu_dire = stack.pop()
    if visited[x][y]:
        visited[x][y] = False
        cnt += 1
    for _ in range(4):
        nx = x + dx[rotate[cu_dire]]
        ny = y + dy[rotate[cu_dire]]
        if 0<= nx <N and 0<= ny<M:
            if visited[nx][ny] and not arr[nx][ny]:
                stack.append((nx,ny,rotate[cu_dire]))
                break
        cu_dire = rotate[cu_dire]
    else:
        reverse_dire = (cu_dire+2)%4
        nx = x + dx[reverse_dire]
        ny = y + dy[reverse_dire]
        if 0<= nx< N and 0<= ny <M and not arr[nx][ny]:
            stack.append((nx,ny,cu_dire))
        else:
            break

print(cnt)

    

이 문제는 문제에 주어진 조건대로 구현을 하는 문제였다. 

 

문제에 주어진 조건대로 구현을 하면 되는데, 여기서 몇가지 주의점이 있다. 보통 DFS나 BFS에서는 시간을 아껴주기 위해, stack에 append 할때 방문을 표시해준다. 하지만 여기서는 한번 청소했던 곳을 다시 방문할 수 있고, 청소는 단 한번만 해주기 때문에, stack에서 빼줄때, 그때 visitied를 방문표시를 해주고, 청소회수를 늘려주었다. 이러는게 문제에 주어진 구현 순서인 1번에 적합한 것 같다.

 

1. 현재 위치를 청소한다.
2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
   1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
   2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
   3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
   4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

 

2.1 ~ 2.2 구간이 중간에 있는 반복문에 있는 부분이다. 여기서는 사전에 작업을 해주었다. 위에 주석에도 있지만, 0,1,2,3을 북동남서로 저장해주고, 그에 해당되는 dx,dy를 구현해주었다. 

그리고, rotate라는 변수에, 인덱스값은 현재의 방향 그리고 값은 왼쪽으로 회전시 나오는 방향을 넣어주었다.

 

평소에는 북남동서등 같은 방향끼리, 하는 경우가 많은데 여기서는 북동남서로 2칸씩 떨어트린 이유는 후진을 구현할때, 이렇게 2칸씩 떨어트려주면 (direction+2)%4 로 하면 쉽게 방향을 구할 수 있기 때문이다. 정 아니면 rotate와 동일하게 후진시 변경되는 리스트를 미리 만들어둬도 된다.

 

 

이렇게 반복문을 다 돌렸는데도 한번도 만족하지 않으면, else로 들어가 2.3~2.4 로직을 진행한다.

후진이 가능하면, stack에 집어넣고, 그렇지 않으면 종료를 해주면 된다.

 

 

구현관련된 문제는 하나씩 단계별로 구현하는 연습을 더 자주해야할것 같다.