백준: 14503 로봇 청소기

문제

14503번: 로봇 청소기

 

문제 풀이

 로봇 청소기의 동작 로직이 정해져고, 그래프가 주어질 때 최대 몇 칸을 청소할 수 있는지 반환하는 문제이다. 해당 문제에서 로봇 청소기는 다음과 같이 작동한다.

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

 

 한 지점에 대해 2번과 같은 탐색 과정을 거친 후, DFS로 다시 호출하였을 때 더 이상 탐색이 진행이 불가능할 경우라면 청소한 칸을 출력하고 프로그램을 종료하도록 한다.

 

코드

from sys import stdin


def dfs(cur_x, cur_y, cur_dir):
    X, Y = 0, 1
    global answer
    dirs = ((-1, 0), (0, 1), (1, 0), (0, -1))

    if graph[cur_x][cur_y] == 1:
        print(answer)
        exit()

    for _ in range(4):
        next_dir = (cur_dir + 3) % 4
        next_x, next_y = cur_x + dirs[next_dir][X], cur_y + dirs[next_dir][Y]

        if not graph[next_x][next_y]:
            graph[next_x][next_y] = 2
            answer += 1
            dfs(next_x, next_y, next_dir)
            return

        cur_dir = next_dir

    # 후진 하는 경우
    dfs(cur_x - dirs[cur_dir][X], cur_y - dirs[cur_dir][Y], cur_dir)

if __name__ == "__main__":
    answer = 1
    n, m = map(int, stdin.readline().split())
    r, c, d = map(int, stdin.readline().split())
    graph = [list(map(int, stdin.readline().split())) for _ in range(n)]
    graph[r][c] = 2
    dfs(r, c, d)

 최초에 작성할 때는 현재 방향에서 다른 방향으로 변화 할 때, L, R, U, D와 같은 딕셔너리를 사용하여서 작성하였다. 하지만 굳이 그럴 필요 없이 나머지 연산을 활용하면 더욱 쉽게 다음 방향을 구할 수 있다.