백준 14503 파이썬

문제

로봇 청소기

백준 14503

풀이

다음과 같은 문제 풀이대로 진행한다.
1. 현재 위치를 청소한다.
2.현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 인접한 칸을 탐색한다.
2-1)왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
2-2)왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
2-3)네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
2-4)네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

from collections import deque

new_direct=[3,0,1,2]
dx=[-1,0,1,0]
dy=[0,1,0,-1]
def clean(start,d):
    global  answer
    place[start[0]][start[1]]=2
    # 첫번째 칸 청소
    q=deque()
    q.append([start[0],start[1],d])
    while q !=[]:
        x,y,d=q.popleft()
        # 왼쪽에 있는 것 먼저 뺀다
        pd=d
        d=new_direct[d]
        new_x = x + dx[d]
        new_y = y + dy[d]
        pre_x = x - dx[pd]
        pre_y = y - dy[pd]
        check=0

        if 0<=new_x<N and 0<=new_y<M and place[new_x][new_y]==0:
            # 1번
			# 이동할 위치가 장소안에 있고 , 청소 가능할 때 
            q.append([new_x,new_y,d])
            # 이동하고, 청소
            place[new_x][new_y]=2
            answer+=1
            continue


        for i in range(4):
            new_i=x+dx[i]
            new_j=y+dy[i]

            if 0<=new_i<N and 0<=new_j<M and place[new_i][new_j]==0:
                check+=1
				# 동서남북 방향에 이동할 수 있는 곳 체크
        if check !=0:
        	# 2-1, 2-2 를 거쳤을 때 이동방향이 있을 때 
            q.append([x,y,d])
		

        if check==0 and place[pre_x][pre_y]==2 :
			# 2-3) 
            q.append([pre_x,pre_y,pd])
            # 후진한다
        elif check==0 and place[pre_x][pre_y]==1 :
			# 2-4)
            return
        





import sys
input=sys.stdin.readline

N,M=map(int,input().split())

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

place=[list(map(int,input().split())) for _ in range(N)]

answer=1

clean([r,c],d)

print(answer)

결과