백준 14503번 - 로봇 청소기

로봇 청소기 문제 바로 가기

풀이 날짜: 2026-01-05

baekjoon 알고리즘 문제 풀이

풀이 코드

import sys
input = sys.stdin.readline
from collections import deque

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

count = 0

n,m = map(int, input().split())
r,c,d = map(int, input().split())
area = []
for _ in range(n):
    area.append(list(map(int, input().split())))

def dfs(x,y,d):
    global count

    if area[x][y] == 0:
        area[x][y] = 2
        count += 1

    for _ in range(4):
        d = (d-1) % 4
        nx = dx[d] + x
        ny = dy[d] + y

        if area[nx][ny] == 0:
            dfs(nx, ny, d)
            return

    back_dir = (d+2)%4
    bx = dx[back_dir] + x
    by = dy[back_dir] + y

    if area[bx][by] == 1:
        return

    dfs(bx,by,d)

dfs(r,c,d)
print(count)
  

문제 핵심 요약:

로봇은 (x, y) 위치에서 방향 d를 바라보며 다음 규칙을 반복한다.

1) 현재 칸이 아직 청소되지 않았으면 청소한다.
2) 왼쪽으로 회전한 뒤, 그 방향의 앞 칸이 청소되지 않은 빈칸(0)이면 그 칸으로 이동한다.
3) 2)의 과정을 4번(4방향) 반복해서도 이동할 칸이 없으면 뒤로 후진한다.
4) 뒤가 벽(1)이면 작동을 멈춘다.

즉, “갈 수 있는 칸을 찾는 과정”이 아니라,
정해진 회전 규칙과 후진 규칙을 그대로 시뮬레이션 해야 정답이 나오는 문제였다.

내가 선택한 풀이 방식: DFS

이 문제는 로봇의 상태가 항상 하나이고, 이동도 한 번에 한 칸씩 “한 경로”로 진행되기 때문에
DFS를 사용했다.

• dfs(x, y, d)
  → “로봇이 (x,y)에서 d 방향을 보고 있을 때, 규칙대로 계속 진행했을 때의 청소 결과를 반영한다.”

중요한 점: DFS를 쓴다고 해서 “모든 경로를 탐색”하는 게 아니다.
DFS는 단지 시뮬레이션 흐름을 재귀로 표현한 도구일 뿐이다.

방향 설계가 제일 중요했다

방향 인덱스는 반드시 문제의 정의와 같아야 한다.

0: 북, 1: 동, 2: 남, 3: 서

따라서 dx, dy는 아래처럼 고정했다.

(0북 1동 2남 3서) dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1]