0317. [BOJ#14503] 로봇 청소기

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

14503번: 로봇 청소기

2 초

512 MB

62316

33861

23012

53.700%

문제

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

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

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

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

입력

첫째 줄에 방의 크기 �$N$과 �$M$이 입력된다. (3≤�,�≤50)$(3 \le N, M \le 50)$  둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 (�,�)$(r, c)$와 처음에 로봇 청소기가 바라보는 방향 �$d$가 입력된다. �$d$가 0$0$인 경우 북쪽, 1$1$인 경우 동쪽, 2$2$인 경우 남쪽, 3$3$인 경우 서쪽을 바라보고 있는 것이다.

셋째 줄부터 �$N$개의 줄에 각 장소의 상태를 나타내는 �×�$N \times M$개의 값이 한 줄에 �$M$개씩 입력된다. �$i$번째 줄의 �$j$번째 값은 칸 (�,�)$(i, j)$의 상태를 나타내며, 이 값이 0$0$인 경우 (�,�)$(i, j)$가 청소되지 않은 빈 칸이고, 1$1$인 경우 (�,�)$(i, j)$에 벽이 있는 것이다. 방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 위치한 모든 칸에는 벽이 있다. 로봇 청소기가 있는 칸은 항상 빈 칸이다.

출력

로봇 청소기가 작동을 시작한 후 작동을 멈출 때까지 청소하는 칸의 개수를 출력한다.

---

제출 코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

di = [-1, 0, 1, 0] # 북 동 남 서
dj = [0, 1, 0, -1]

def clean(si, sj, dir_):
    global cnt

    while True:
        clean = 0    
        for _ in range(4):
            dir_ = (dir_+3) % 4
            ni = si + di[dir_]
            nj = sj + dj[dir_]

            if 0 <= ni < N and 0 <= nj < M and arr[ni][nj] == 0:
                if visited[ni][nj] == False:
                    visited[ni][nj] = True
                    cnt += 1
                    si = ni
                    sj = nj
                    clean = 1
                    break
                
        # 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우(다 방문한 경우)
        if clean == 0:
            if arr[si-di[dir_]][sj-dj[dir_]] == 1: # 벽인 경우
                print(cnt)
                break
            else: # 벽이 아닌 경우
                si, sj = si-di[dir_], sj-dj[dir_]



N, M = map(int, input().split())
r, c, dir_ = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
visited = [[False] * M for _ in range(N)]

cnt = 1
visited[r][c] = True
clean(r, c, dir_)

재귀로 풀려고 하다가 청소기가 90도씩 돌면서 확인하는게 재귀로 너무 힘들다는 걸 깨닫고 엎고 다시시도한 문제

원래 방향을 벡터로 북서남동으로 설정하고 반복문으로 돌리려고 했지만 초기위치에서 원하는만큼(반시계) 돌릴수가 없어서 포기했다. (dir + 3) % 4 로 합류하고 구현으로 풀었다,.

최근 문제들에서 while 문 사용이 잦은데 익숙해져야겠다