백준 14503 | 로봇 청소기 (DFS)

문제 출처 : https://www.acmicpc.net/problem/14503

문제

• 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.
• 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다.
• 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다.
• 지도의 북쪽에서부터 r번째, 서쪽에서부터 c번째로 위치한 칸은 (r, c)로 나타낼 수 있다.
• 로봇 청소기는 다음과 같이 작동한다.
  1. 현재 위치를 청소한다.
  2. 현재 위치에서 다음을 반복하면서 인접한 칸을 탐색한다.
     1. 현재 위치의 바로 왼쪽에 아직 청소하지 않은 빈 공간이 존재한다면, 왼쪽 방향으로 회전한 다음 한 칸을 전진하고 1번으로 돌아간다. 그렇지 않을 경우, 왼쪽 방향으로 회전한다. 이때, 왼쪽은 현재 바라보는 방향을 기준으로 한다.
     2. 1번으로 돌아가거나 후진하지 않고 2a번 단계가 연속으로 네 번 실행되었을 경우, 바로 뒤쪽이 벽이라면 작동을 멈춘다. 그렇지 않다면 한 칸 후진한다.

입력

• 첫째 줄에 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 50)
• 둘째 줄에 로봇 청소기가 있는 칸의 좌표 (r, c)와 바라보는 방향 d가 주어진다. d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽을 바라보고 있는 것이다.
• 셋째 줄부터 N개의 줄에 장소의 상태가 북쪽부터 남쪽 순서대로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 빈 칸은 0, 벽은 1로 주어진다. 지도의 첫 행, 마지막 행, 첫 열, 마지막 열에 있는 모든 칸은 벽이다.
• 로봇 청소기가 있는 칸의 상태는 항상 빈 칸이다.

출력

• 로봇 청소기가 청소하는 칸의 개수를 출력한다.

문제 접근 방법

• 조건에 맞게 구현하면 문제를 풀 수 있지만 조심해야할 부분
• 청소를 다 하고 돌아오고 종결조건이 벽을 만나고 재귀로 돌아올 때 return 해야한다.

if 0 <= new_row < n and 0 <= new_col < m:
	if graph[new_row][new_col] == 0 and not visited[new_row][new_col]:
    	solution(new_row, new_col, left)
        return

• left를 구할 때는 circular한 규칙은 % 나머지를 통해서 풀 수 있다.
  • ↑ : 3 2 1 0
  • ← : 2 1 0 3
  • ↓ : 1 0 3 2
  • → : 1 0 3 2

코드

def solution(row, col, direct):
    global answer, graph, visited

    if not visited[row][col]:
        answer += 1
        visited[row][col] = True

    for i in range(4):
        left = (direct - i - 1) % 4
        new_row, new_col, = row + dx[left], col + dy[left]

        if 0 <= new_row < n and 0 <= new_col < m:
            if graph[new_row][new_col] == 0 and not visited[new_row][new_col]:
                solution(new_row, new_col, left)
                return

    back = (direct + 2) % 4
    new_row, new_col, = row + dx[back], col + dy[back]

    if graph[new_row][new_col]:
        return
        
    solution(new_row, new_col, direct)


n, m = map(int, input().split())
r, c, d = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[0] * m for _ in range(n)]
answer = 0
dx, dy = (-1, 0, 1, 0), (0, 1, 0, -1)

solution(r, c, d)
print(answer)