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()
ps/problems/boj/14503.txt · 마지막으로 수정됨: 2022/09/13 16:21 저자 teferi
토론