백준 알고리즘 14503번 로봇청소기 풀이 with Python

문제 링크:  https://www.acmicpc.net/problem/14503

14503번: 로봇 청소기

 

문제는 아래의 이미지에 설명되어있습니다.

문제를 읽어보시면 로봇 청소기가 각 단계마다 동서남북을 탐색해야 하므로 bfs로 문제를 해결해야 함을 직관적으로 생각하실 수 있습니다. 저는 bfs와 재귀 호출을 사용하여 문제를 해결하였는데, 재귀 호출 사용 시 필요 없는 함수 호출을 return 하는 것을 생각하는데 오래 걸려 시간을 많이 소비하였습니다. 제가 해결한 코드는 아래와 같습니다. 

n,m=map(int,input().split()) #n,m에 가로 세로 크기를 받습니다.
r1,c1,d1=map(int,input().split()) # r1,c1,d1을 통해 로봇청소기의 처음 위치와 방향을 입력받습니다.
map1=[] # map1에 로봇청소기가 청소할 필드를 받습니다.
# 필드의 세로크기만큼 반복하여 map1에 필드값을 입력합니다.
for i in range(n):
	'''input().split()함수를 사용하여 입력값을 공백단위로 입력받고, 
    각 입력값마다 int함수를 적용하기위해 map함수를 사용합니다. '''
    map1.append(list(map(int,input().split())))
#로봇청소기가 청소한 자리수를 저장하기 위한 변수 count를 선언합니다.
count=0
# 북 동 남 서
gx=[-1,0,1,0]
gy=[0,1,0,-1]
# 이번 문제의 메인 함수인 cleaner함수를 정의합니다.
def cleaner(r,c,d):
	#함수안에서 함수밖의 변수를 사용하기 위해 global 을 사용합니다.
    global count
    if map1[r][c]==0:
        count+=1
        map1[r][c]=2
    for i in range(1,5):
    	#기존 방향에서 왼쪽방향으로 돌아야 하기때문에 for문을 사용합니다.
        #try except은 리스트의 인덱스 에러가 발생할 경우를 대비하여 사용하였습니다.
        try:
        	# 4방향으로 계속 돌아야하기때문에 모듈러함수인 %을 이용합니다.
            new_d = (d-i)%4
            if map1[r+gx[new_d]][c+gy[new_d]]==0:
            	#만약 현재 가르키는 방향이 청소하지않았을 경우 청소를 합니다.
                cleaner(r+gx[new_d],c+gy[new_d],new_d)
                return
        except:
            continue
    #위와 마찬가지로 리스트 인덱스에러가 발생하였을 경우를 대비하여 try except문을 사용하였습니다.
    try:
    	# 후진하였을 때 벽이 아니면 후진을 하도록 하였습니다. 만약 벽이라면 함수를 종료시킵니다.
        if map1[r+gx[(d-2)%4]][c+gy[(d-2)%4]]!=1:
            cleaner(r+gx[(d-2)%4],c+gy[(d-2)%4],d)
        else:
            return
    except:
        return
cleaner(r1,c1,d1)
print(count)