사용자 도구

사이트 도구


ps:problems:boj:14503

로봇 청소기

ps
링크acmicpc.net/…
출처BOJ
문제 번호14503
문제명로봇 청소기
레벨골드 5
분류

시뮬레이션

시간복잡도O(NM)
인풋사이즈N<=50, M<=50
사용한 언어Python
제출기록32468KB / 92ms
최고기록52ms
해결날짜2022/09/13

풀이

  • 그냥 시키는대로 시뮬레이션하면 되는 문제.
  • 진행 방향을 회전시키는 것을 구현하는 것은, 동서남북 4방향을 배열에 넣어두고, 현재 방향을 인덱스로 해서 방향을 가져오는 식으로 구현하는 것이 보통일것이다. 회전하면 인덱스를 1증가시키는 식으로. 그렇지만 여기에서는 덱에 4방향을 넣어두고, 회전하는 것을 그대로 덱을 로테이트 하는 식으로 처리했다. 현재 방향의 인덱스를 따로 갖고있을 필요가 없고, deq[0]이 항상 진행 방향, deq[1]이 왼쪽방향이 된다. 좀더 깔끔한것 같다
  • 액션 1번을 처리하는 것은 O(1). 최악의 경우에는 모든 칸을 이동해야 하므로 시간복잡도는 O(N*M)이 된다

코드

"""Solution code for "BOJ 14503. 로봇 청소기".

- Problem link: https://www.acmicpc.net/problem/14503
- Solution link: http://www.teferi.net/ps/problems/boj/14503

Tags: [Simulation]
"""

import collections
import sys

DELTA = collections.deque([(-1, 0), (0, -1), (1, 0), (0, 1)])
DIRT = '0'
WALL = '1'
CLEAN = '2'


def main():
    N, M = [int(x) for x in input().split()]
    r, c, d = [int(x) for x in input().split()]
    grid = [input().split() for _ in range(N)]

    answer = 0
    DELTA.rotate(d)
    while grid[r][c] != WALL:
        if grid[r][c] == DIRT:
            grid[r][c] = CLEAN
            answer += 1
        dr, dc = DELTA[1]
        nr, nc = r + dr, c + dc
        if grid[nr][nc] == DIRT:
            r, c = nr, nc
            DELTA.rotate(-1)
        elif all(grid[r + dr][c + dc] != DIRT for dr, dc in DELTA):
            dr, dc = DELTA[2]
            r, c = r + dr, c + dc
        else:
            DELTA.rotate(-1)
            
    print(answer)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
N H​ X M M
 
ps/problems/boj/14503.txt · 마지막으로 수정됨: 2022/09/13 16:21 저자 teferi