본문으로 건너뛰기

14503 - 로봇 청소기

info
  • 문제 보기: 14503 - 로봇 청소기
  • 소요 시간: 💥1시간 6분
  • 풀이 언어: python
  • 체감 난이도: 3️⃣
  • 리뷰 횟수: ✅

풀이 키워드​

스포주의

구현


풀이 코드​

info
  • 메모리: 31120 KB
  • 시간: 36 ms
import sys
input = sys.stdin.readline

dy = [-1, 0, 1, 0] # 북 동 남 서
dx = [0, 1, 0, -1]

def solution():
    n, m = map(int, input().split())
    r, c, d = map(int, input().split())
    
    room = [0] * (n)
    for i in range(n):
        room[i] = list(map(int, input().split()))
        
    ans = 1 # 맨 처음 위치를 청소하고 시작
    room[r][c] = -1
    y, x = r, c
    
    while True:
        cleaned = False
        
        for _ in range(4):
            d = (d + 3) % 4 # 반시계 회전
            ny = y + dy[d]
            nx = x + dx[d]
            
            if room[ny][nx] == 0: # 3. 청소 안되어있음
                room[ny][nx] = -1
                ans += 1 # 청소하고
                y, x = ny, nx
                cleaned = True
                break # 이동 후 다시 4방향 탐색
            
        if not cleaned: # 2. 4방향 다 청소할 곳 없음
            ty = y - dy[d]
            tx = x - dx[d]
            if room[ty][tx] == 1: # 후진했는데 벽일 경우
                return ans
            else:
                y, x = ty, tx


if __name__ == '__main__':
    print(solution())

풀이 해설​

두 가지 사항이 중요한 문제이다.

  1. 방향 전환 구현
  2. 문제에 작성된 조건의 적절한 로직화

방향 전환은 방향 벡터 느낌으로 구현하면 되고

방향 전환을 인덱스로 조정하되, 순환하므로 modulo를 활용한다.

dy = [-1, 0, 1, 0] # 북 동 남 서
dx = [0, 1, 0, -1]

d = (d + 3) % 4 # 반시계 회전
ny = y + dy[d]
nx = x + dx[d]

조건의 로직화는 약간 머리를 굴려야 한다.

우선 주어진 조건을 읽어보면 다음과 같다.

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

여기서 1번은 그리 중요한 조건이 아니다. 왜냐하면 3번에서 칸 이동 후 처리하면 되기 때문이다.

따라서 2, 3번이 분기문으로 구현해야 하는 주요 조건이다.

이 부분만 캐치하면 나머지는 그럭저럭...


메모​

  • ㅁㄴㅇㄹ