[Baekjoon 14053] 로봇청소기

문제

💛Ⅴ [Baekjoon 14503 - 로봇청소기]

문제 풀이 방법

처음에는 DFS 재귀 문제로 접근했었다. DFS로 접근하면 다시 후진하는 경우를 조건문으로 명시하지 않고 자동으로 되돌아갈 수 있다고 생각했었지만 아니였다..ㅎ 벽이 아닌 청소한 영역인 경우에만 후진할 수 있기 때문에 이 부분을 구현하기 위해 재귀가 아닌 반복문으로 구현하였다.

1. 현재 위치를 청소할 수 있다면 청소하고 answer + 1을 한다.
2. 왼쪽 방향부터 청소가 가능한 구역이 있는지 탐색한다.
   1. 청소할 수 있는 구역이 있는 경우, flag(네 방향 중에 청소 가능한 구역이 있는지)를 True로 바꿔주고 다시 1로 돌아간다.
3. 청소할 수 있는 구역이 없는 경우, 후진을 한다.
   1. 후진하고자 하는 영역이 벽이 아닌 청소한 영역인 경우, 후진을 하고 다시 2로 돌아간다.
   2. 후진하고자 하는 영역이 벽인 경우, 후진이 불가능하므로 반복문을 탈출한다.

풀이 코드

Python

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
r, c, d = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
answer = 0

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

x, y, direct = r, c, d
while True:
    if graph[x][y] == 0:
        graph[x][y] = 2 # 현재 위치 청소
        answer += 1

    flag = False # 네 방향 중에 청소 가능한 구역이 있는지
    for _ in range(4): # 왼쪽 방향 부터 탐색 진행
        direct = direct-1 if direct != 0 else 3 # 현재 방향의 왼쪽
        n_x = x + dx[direct]
        n_y = y + dy[direct]
        if 0 < n_x < N-1 and 0 < n_y < M-1 and graph[n_x][n_y] == 0: # 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면
            x, y = n_x, n_y
            flag = True
            break
    if not flag: # 네 방향 모두 청소가 이미 되어있거나 벽인 경우, 후진
        n_x = x - dx[direct]
        n_y = y - dy[direct]
        if 0 < n_x < N - 1 and 0 < n_y < M - 1 and graph[n_x][n_y] == 2:
            x, y = n_x, n_y
            flag2 = True
            continue
        break

print(answer)