[BOJ] 14503. 로봇 청소기

문제

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

• 구현 문제는 항상 조건이 길~어서 읽다가 지치는 감이 있다
• 그래도 착실히 구현만 하면 되는 문제!

---

 

주요 아이디어

• 북동남서 (0,1,2,3) 인덱스 넘버
• 순회를 할 때에는 "반시계방향"으로 한 다는 점에 주의!
• 방문처리는 숫자 2로 진행 (별도의 visited 필요 X)

 

---

 

코드 구현 (Python 3)

from collections import deque

N, M = map(int, input().split())
r, c, d = map(int, input().split())
cnt = 0

# 북동남서
direction = [[-1, 0], [0, 1], [1, 0], [0, -1]]
graph = []

for _ in range(N):
    graph.append(list(map(int, input().split())))

queue = deque()
# 큐에 시작 좌표, 현재 방향 추가
queue.append([r, c, d])

while queue:
    y, x, cur_d = queue.popleft()

    # 청소 안된 경우
    if graph[y][x] == 0:
        graph[y][x] = 2; cnt += 1 # 방문 처리

    # 인접 4칸 탐색 -> 현재 방향으로부터 '반'시계방향으로
    cleaned = False
    for i in range(1, 5):
        new_d = (cur_d - i) % 4
        dy, dx = direction[new_d]
        ny, nx = y + dy, x + dx

        # 청소되지 않은 빈 칸인 경우
        if 0 <= ny < N and 0 <= nx < M and graph[ny][nx] == 0:
            queue.append([ny, nx, new_d])
            cleaned = True
            break
    
    # 청소되지 않은 빈 칸이 없는 경우
    if cleaned == False:
        dy, dx = direction[cur_d] # 한 칸 후진
        ny, nx = y - dy, x - dx
        # 한 칸 후진하기 혹은 종료 - 청소한 칸으로도 후진은 가능
        if 0 <= ny < N and 0 <= nx < M and graph[ny][nx] != 1:
            queue.append([ny, nx, cur_d]) # 방향은 유지
        else:
            # 벽에 부딪히면 반복문 탈출
            break

print(cnt)

 

---

 

제출 결과