로봇 청소기 ( 14503 번 )

14503번: 로봇 청소기

 

---

🧠 알고리즘

• 시뮬레이션 + 방향 전환 & 상태 기반 반복 탐색

 

✔️ 동작 방식

[ 문제 핵심 아이디어 ]

로봇이 다음 규칙에 따라 방을 청소하는 과정을 그대로 시뮬레이션으로 구현하는 문제.

1. 현재 위치가 청소되지 않았으면 청소한다.
2. 주변 4칸 중 청소되지 않은 빈 칸이 있는지 확인한다.
   • 있다면 왼쪽으로 회전하며, 처음 발견되는 미청소 칸으로 이동
   • 없다면 바라보는 방향을 유지하고 뒤로 후진
3. 후진도 불가능(=벽)하면 작업 종료

즉, 방문 여부와 위치/방향 상태를 기반으로 순차적으로 처리하는 시뮬레이션 문제이다.

 

 

[ 주요 로직 요약 ]

1) 방향 정의

gogo = {0: (-1, 0), 1: (0, 1), 2: (1, 0), 3: (0, -1)}

• 0: 북, 1: 동, 2: 남, 3: 서
• 이동의 편의를 위해 방향별 델타를 저장

 

2) 회전/후진 로직

• 왼쪽 회전: (d + 3) % 4
• 후진: (d + 2) % 4

 

3) 메인 반복 구조

- 현재 칸 청소

if map_list[r][c] == 0: answer += 1 map_list[r][c] = 2 # 방문 표시

 

- 주변 4칸 탐색하며 왼쪽 회전

• 4번 왼쪽으로 돌며
• 미청소 칸(0)이 나타나면 해당 칸으로 이동하고 루프 탈출

- 미청소 칸이 없으면 후진

• 후진한 위치가 벽(1)이면 종료

---

 

🧾 코드

import sys

"""
1) 현재 칸 청소
2) 주변 4칸 청소 되지 않은 빈 칸이 없으면,,
    - 바로 보는 방향 유지하고 한 칸 후진
    - 후진 할수 없는 벽이면 break
3) 주변 4칸 중 청소되지 않는 빈 칸이 있는 경우,,
    - 반시계로 회전 하며
    - 바라보는 방향 이 청소가 되지 않는 빈칸이면 전진

## 방의 가장 북, 남, 서, 동 >> 모든 칸에 벽이 있음
즉, 가장자리는 무조건 벽으로 래핑되어 있는 구조

- 방향
0: 북, 1: 동, 2: 남, 3: 서
"""

def _turn(num):
    """
        회전 로직
        0 >> 3
        1 >> 0
        2 >> 1
        3 >> 2
        - (num + 3) % 4
    """
    return (num + 3) % 4
    

def _back(num):
    """
        후진 로직
        0 >> 2
        1 >> 3
        2 >> 0
        3 >> 1
        - (num + 2) % 4
    """
    return (num + 2) % 4

def _main(r, c, head):
    answer = 0
    gogo = {0: (-1, 0), 1: (0, 1), 2: (1, 0), 3: (0, -1)}

    while True:
        if map_list[r][c] == 0: # 현재 칸 청소 ~
            answer += 1
            map_list[r][c] = 2

        check = False
        for _ in range(4):
            head = _turn(head)
            go_r, go_c = gogo[head]
            nr, nc = r + go_r, c + go_c

            if (map_list[nr][nc] == 0): # 청소 되지 않은 빈 칸!!
                r, c = nr, nc
                check = True
                break
                
        if not check: # 청소 되지 않은 빈 칸이 없는 경우, 후진 go ~
            back_point = _back(head)
            go_r, go_c = gogo[back_point]
            nr, nc = go_r + r, go_c + c
            
            if map_list[nr][nc] == 1:
                break

            r, c = nr, nc

    return answer
    

n, m = map(int, sys.stdin.readline().rstrip().split())
r, c, head = map(int, sys.stdin.readline().rstrip().split())
map_list = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]

print(_main(r, c, head))

---

 

⏱️ 시간 복잡도

while True : 2차형 각 칸을 한번 씩 방문하여 청소 ( 이차형 시간 )

해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )