[알고리즘][파이썬]14503-로봇청소

문제

 

 

문제 이해

 

로봇청소기가 벽이 아닌 구간을 돌아다니며 청소를 하는 문제이다. 

방의 크기/청소기 위치, 청소기 방향이 주어지고 벽은 1, 빈칸은 0으로 된  N*M 값을 받게 된다.

아래와 같이 로봇 움직임의 규칙이 나와있는데 이에 대한 이해와 숙지가 굉장히 중요한 거 같다. 

---

1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
2. 현재 칸의 주변 4$4$칸 중 청소되지 않은 빈 칸이 없는 경우,
   1. 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
   2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
3. 현재 칸의 주변 4$4$칸 중 청소되지 않은 빈 칸이 있는 경우,
   1. 반시계 방향으로 90∘$90^\circ$ 회전한다.
   2. 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈칸인 경우 한 칸 전진한다.
   3. 1번으로 돌아간다.

---

+나의 실수 : 주변 4칸 중 청소되지 않은 빈칸이 있는 경우 반시계 방향으로 90도 회전한 후 바라보는 부분이 청소가 

가능한지 판단해야하는데 바라보는 부분을 먼저 확인하고 청소가 불가능할 때부터 90도 회전하는 것인지 아는 바람에 

코드 작성에 시간을 많이 소요했다. 😅

문제를 꼼꼼히 읽고 파악하는 것이 무엇보다 중요하다

 

 

코드 설계

 

조건에 따라 계속해서 청소와 주변탐색을 반복하는 특징이 있는 문제이다. 

따라서 재귀함수를 사용했다.

 

clean이라는 함수를 통해 청소를 할 때마다 count변수로 횟수를 업로드했다. 

청소 후 주변을 탐색하고 조건에 맞춰 다시 clean함수를 호출하거나 종료하도록 작성했다. 

 

<현재 칸에서 주변 시계방향으로 탐색 후 결과에 따른 로봇의 동작>

1. 0자리 발견 -> 해당자리를 인자로 clean함수 호출
2. 0자리 없음 -> 후진 -> 후진가능 : clean함수 호출 / 후진 불가능: 함수 종료 

+후진 가능 : 1이 아닐 때

+후진 불가능 : 1일 때

 

코드

import sys

n,m = map(int,sys.stdin.readline().strip().split())
x,y,z = map(int,sys.stdin.readline().strip().split())
g =[]
for _ in range(n):
    g.append(list(map(int,sys.stdin.readline().strip().split())))
visited=[[False]*m for _ in range(n)]


#벽인지와 청소가 가능한지 판별하는 함수다.
def check(x,y):
    if g[x][y] == 1:
        return 1  #벽일때
    if visited[x][y] :
        return 2  #이미 청소했을 때
    return 0


#청소할 자리를 받는다. 
def clean(x,y,z,count): #자리+방향+count
    if(check(x,y)==0):  #청소한 자리 수 세기
        count+=1

    dx = [-1,0,1,0]
    dy = [0,1,0,-1] #0,1,2,3 순서로 둠
    visited[x][y] = True # 청소한 자리 기록하기

    Z = z
    #1)0발견 ->clean 함수 호출
    for _ in range(4):
        Z -=1   #시계방향을 돌리기
        if(Z<0): Z =3
        if(check(x+dx[Z],y+dy[Z])==0):
            clean(x+dx[Z],y+dy[Z],Z,count)
            return 
        
    #2)0발견 못함 -> 후진
    if check(x-dx[z],y-dy[z])!=1: # 벽이 아니면 후진
        clean(x-dx[z],y-dy[z],z,count)
        return 
    else: #벽이면 중지
        print(count)
        return 
           


clean(x,y,z,0)

 

 

 

추가 코드

import sys

N,M = map(int, sys.stdin.readline().strip().split())
x,y,z = map(int, sys.stdin.readline().strip().split())
g =[]

for i in range(N):
    g.append(list(map(int,sys.stdin.readline().strip().split())))


count = 0
dx = [-1,0,1,0]#0,1,2,3
dy = [0,1,0,-1]

def clean(x,y,z):
    global count
    
    #청소 
    if(g[x][y]==0):
        g[x][y] = 2
        count +=1
    
    #탐색
    Z= z
    #청소할 방이 있는가
    for i in range(4):
        Z = (Z+3) % 4
        if(g[x+dx[Z]][y+dy[Z]]==0):
            clean(x+dx[Z],y+dy[Z],Z)
            return
    #후진이 가능한가
    if(g[x-dx[z]][y-dy[z]]!=1):
        clean(x-dx[z],y-dy[z],z)
        return 
    else:
        return count


clean(x,y,z)
print(count)