[Python] 14503번 로봇 청소기

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

14503번: 로봇 청소기

---

 

24/01/07

 

 

구현/시뮬레이션 문제로, 문제에서 요구하는 바를 그대로 구현하면 맞았습니다를 받을 수 있는 정직한 문제다. 

---

 

문제 접근 방식:

 

 

이 문제를 접근할 때에 기존에 이렇게 $N \times M$형태의 map이 주어지고 이 위에서 BFS나 DFS를 진행하는 문제를 풀어봤다면 어떻게 접근할지 조금은 감이 잡힐 수 있을 것이다.

 

북, 동, 남, 서 방향은 각각 $(-1, 0), (0, 1), (1, 0), (0, -1)$로 움직임을 표현할 수 있다.

 

문제에서 나온 그대로를 구현하면 된다.

 

주변 $4$칸 중 청소할 칸이 존재하지 않는다면, 바라보는 방향을 유지한 채로 한 칸 뒤로 가라고 했다.

 

즉, 이는 바라보는 방향의 반대 방향으로 한 칸을 가라는 뜻이다.

 

즉, $0$번 방향이면 $2$번, $2$번 방향이면 $0$번 방향으로 가고 $1$번 방향이면 $3$번, $3$번 방향이면 $1$번 방향으로 한 칸 움직이면 된다.

 

이에 대한 구현은 방향에 $+2$를 해주고 $4$를 나눠줌으로써 쉽게 구현할 수 있다.

 

너비 우선 탐색이나 깊이 우선 탐색과 같이 $4$방향을 체크할 때 범위 또한 체크해 주었다.

 

사실은 문제 조건에 의해 모든 테두리가 벽으로 둘러싸여 있으므로 이렇게 체크를 안해도 맞았습니다를 받을 수 있다.

 

반시계방향으로 $90$도 회전하는 것은 기존 방향에 $1$을 빼주고 $4$를 나눠줌으로써 해결하였다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 14503번 로봇 청소기
# 구현, 시뮬레이션
import sys
input = sys.stdin.readline

N, M = map(int, input().rstrip().split())
r, c, d = map(int, input().rstrip().split())
move = [(-1, 0), (0, 1), (1, 0), (0, -1)]
room = [list(map(int, input().rstrip().split())) for _ in range(N)]
cleaned = 0
while True:
    if room[r][c] == 0:
        room[r][c] = 2
        cleaned += 1
    no_clean = []
    for i in range(4):
        nr, nc = r+move[i][0], c+move[i][1]
        if 0 <= nr < N and 0 <= nc < M and room[nr][nc] == 0:
            no_clean.append((nr, nc))
    if no_clean == []:
        nd = (d+2)%4
        nr, nc = r+move[nd][0], c+move[nd][1]
        if 0 <= nr < N and 0 <= nc < M and room[nr][nc] != 1:
            r, c = nr, nc
        else:
            break
    else:
        d -= 1
        d %= 4
        nr, nc = r+move[d][0], c+move[d][1]
        if 0 <= nr < N and 0 <= nc < M and room[nr][nc] == 0:
            r, c = nr, nc
print(cleaned)