알고리즘/백준 문제풀이

[boj] 백준 14503 로봇 청소기 python 풀이

감자156 2023. 8. 10. 15:29
반응형

문제

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

 

14503번: 로봇 청소기

첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$  둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽

www.acmicpc.net

 

문제 풀이

구현문제. for ~ else문을 새롭게 알게됨. for문 돌다가 break로 끊기지 않았으면 for문 다 돌고 else문이 실행됨. 유용하다!

 

코드

1) deque 사용 X ( 훨 빠름 )

import sys
input = sys.stdin.readline

N, M = map(int,input().split())
cx, cy, cd = map(int,input().split())

MAP = [list(map(int,input().split())) for _ in range(N)]
move = [(-1,0),(0,1),(1,0),(0,-1)]
res = 0

while True:
    if MAP[cx][cy] == 0: #청소
        res += 1
        MAP[cx][cy] = 2

    for d in range(4): # 주변 4칸 중 청소할 칸 있으면
        tx, ty = move[(cd-d-1)%4]
        nx = tx + cx
        ny = ty + cy

        if 0<=nx<N and 0<=ny<M and MAP[nx][ny] == 0:
            cx, cy, cd = (nx,ny,(cd-d-1)%4)
            break
            
    else: # 주변에 청소안한 빈칸 없음
        tx, ty = move[cd%4]
        nx = cx - tx
        ny = cy - ty
        if MAP[nx][ny] != 1: #후진 가능?
            cx, cy, cd = nx, ny, cd
            continue

        if MAP[nx][ny] == 1: # 후진 불가능 뒤에 벽
            break

print(res)

 

2) collections.deque 사용 

import sys
input = sys.stdin.readline
import collections

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

MAP = [list(map(int,input().split())) for _ in range(N)]
move = [(-1,0),(0,1),(1,0),(0,-1)]
res = 0

q = collections.deque()
q.append((r,c,d))

while q:
    cx, cy, cd = q.popleft()
    if MAP[cx][cy] == 0: #청소
        res += 1
        MAP[cx][cy] = 2

    for d in range(4): # 주변 4칸 중 청소할 칸 있으면
        tx, ty = move[(cd-d-1)%4]
        nx = tx + cx
        ny = ty + cy

        if 0<=nx<N and 0<=ny<M and MAP[nx][ny] == 0:
            q.append((nx,ny,(cd-d-1)%4))
            break
            
    else: # 주변에 청소안한 빈칸 없음
        tx, ty = move[cd%4]
        nx = cx - tx
        ny = cy - ty
        if MAP[nx][ny] != 1: #후진 가능?
            q.append((nx, ny, cd))
            continue

        if MAP[nx][ny] == 1: # 후진 불가능 뒤에 벽
            break

print(res)
반응형