[백준] 14503. 로봇 청소기/Python - Gold5

❓문제

https://www.acmicpc.net/problem/14503

성능 요약

메모리: 109544 KB, 시간: 92 ms

 

 

문제 설명

로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

로봇 청소기가 있는 방은 N×MN×M 크기의 직사각형으로 나타낼 수 있으며, 1×11×1 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 방의 각 칸은 좌표 (r,c)(r,c)로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가 (0,0)(0,0), 가장 남쪽 줄의 가장 동쪽 칸의 좌표가 (N−1,M−1)(N−1,M−1)이다. 즉, 좌표 (r,c)(r,c)는 북쪽에서 (r+1)(r+1)번째에 있는 줄의 서쪽에서 (c+1)(c+1)번째 칸을 가리킨다. 처음에 빈 칸은 전부 청소되지 않은 상태이다.

로봇 청소기는 다음과 같이 작동한다.

1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
2. 현재 칸의 주변 44칸 중 청소되지 않은 빈 칸이 없는 경우,
   1. 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
   2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
3. 현재 칸의 주변 44칸 중 청소되지 않은 빈 칸이 있는 경우,
   1. 반시계 방향으로 90∘90∘ 회전한다.
   2. 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
   3. 1번으로 돌아간다.

✍🏻풀이

https://thisismi.tistory.com/entry/%EB%B0%B1%EC%A4%80-14503%EB%B2%88-%EB%A1%9C%EB%B4%87-%EC%B2%AD%EC%86%8C%EA%B8%B0-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%ED%92%80%EC%9D%B4

[백준] 14503번 로봇 청소기 파이썬 풀이

위 사이트를 참고해서 풀었습니다.

💻코드

import sys

input = sys.stdin.readline

N, M = map(int, input().strip().split())
r, c, d = map(int, input().strip().split())
room = [list(map(int, input().strip().split())) for _ in range(N)]
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

def checked(r, c):
    for i in range(4):
        nr, nc = r + dr[i], c + dc[i]
        if 0 <= nr < N and 0 <= nc < M and room[nr][nc] == 0:
            return True
    return False

def cleaning(r, c, d):
    global room
    ans = 0

    while True:
        if room[r][c] == 0:
            ans += 1
            room[r][c] = 2

        if checked(r, c):
            for i in range(1, 5):
                dir = (d - i) % 4
                nr, nc = r + dr[dir], c + dc[dir]

                if 0 <= nr < N and 0 <= nc < M and room[nr][nc] == 0:
                    d = dir
                    r, c = nr, nc
                    break

        else:
            nr, nc = r - dr[d], c - dc[d]
            if 0 > nr or nr >= N or 0 > nc or M <= nc or room[nr][nc] == 1:
                return ans
            r, c = nr, nc


print(cleaning(r, c, d))

📍후기

처음에는 DFS로 접근했다가 생각해보니 이렇게 하면 1번으로 다시 돌아가지 않아서 while문으로 그냥 구현하면 되는 걸 뒤늦게 생각했다...