[백준] 14503 로봇 청소기 [Python]

 

이 문제를 처음 봤을 때 지문을 잘못이해해서 왼쪽으로90도 회전하고 이동하고를 같은 자리를 무한 반복하는 줄 알았다..

 

질문 게시판을 가보니 나와 같은 문제를 갖고 있는 사람들이 많아서 질문을 읽고 이해를 하게되었습니다.

 

우선 문제의 풀이방법을 생각해보면 dfs,bfs 방식으로 접근할 수 있고 제가 풀이한 방식은 dfs의 방식을 사용했습니다. 

 

    N,M = map(int,s.readline().split())
    r,c,d = map(int,s.readline().split())
    cnt=0
    #북동남서순서
    dx=[-1,0,1,0]
    dy=[0,1,0,-1]
    arr = [list(map(int,s.readline().split())) for _ in range(N)]
    dfs(r,c,d)

 

처음 주어진 방향의 값이(d) 0이므로 dx,dy를 북, 동, 남, 서 기준으로 선언해주었습니다. 위의 값을 토대로 회전에 필요하므로 네 방향을 탐색할때 이 방식을 많이 사용하므로 익숙해지시면 좋을 것 같습니다.

 

 

def dfs(x,y,direct):
    global cnt
    #현재칸 청소하면 2로 넣어줌
    if arr[x][y]==0:
        arr[x][y]=2
        cnt+=1
    
    #4방향이 안비어있는경우 체크하기위한 변수
    check =1
    #왼쪽으로 90도 회전을 시작으로 4방향 검사
    for _ in range(4):
        #왼쪽으로 90도 회전
        direct = (direct + 3)%4
        nx = x+dx[direct]
        ny = y+dy[direct]
        
        if not arr[nx][ny]:
            dfs(nx,ny,direct)
            check=0
            return
    #check가 1이면 네방향모두 안비어있는 경우
    if check==1:
        #후진하는 방향
        direct = (direct+2)%4
        nx = x+dx[direct]
        ny = y+dy[direct]
        #배열의 벽이아니면 후진
        if arr[nx][ny] != 1:
            dfs(nx,ny,(direct+2)%4)

dfs 함수부분의 코드입니다.

우선 배열값이 벽(1)과 비어있는 칸(0)으로 되있으므로 비어있는 칸으로 들어갈 경우 값을 2로 바꿔주어 표시를 해줍니다. 

그리고 네 방향이 모두 비어있지 않은 경우를 체크하기위해 check변수를 만들어서 확인합니다.

네 방향중 비어있는 칸이 있다면 그 방향으로 이동하고 cnt값을 1 증가시켜서 총 몇칸을 이동했는지 검사합니다.

 

후진하는 방법은 제가 간 방향에서 dx,dy를 활용해 현재 값에 +2를 해주고 %4를 해주면 뒤로가는 방향을 찾게됩니다. 벽이 아닌 값으로 뒤를 가면서 bfs 재귀를 호출하면 청소기가 청소할 수 있는 부분을 확인할 수 있습니다.

 

전체 코드

from sys import stdin as s 
from collections import deque
s=open('input.txt','rt')

def dfs(x,y,direct):
    global cnt
    #현재칸 청소하면 2로 넣어줌
    if arr[x][y]==0:
        arr[x][y]=2
        cnt+=1
    
    #4방향이 안비어있는경우 체크하기위한 변수
    check =1
    #왼쪽으로 90도 회전을 시작으로 4방향 검사
    for _ in range(4):
        #왼쪽으로 90도 회전
        direct = (direct + 3)%4
        nx = x+dx[direct]
        ny = y+dy[direct]
        
        if not arr[nx][ny]:
            dfs(nx,ny,direct)
            check=0
            return
    #check가 1이면 네방향모두 안비어있는 경우
    if check==1:
        #후진하는 방향
        direct = (direct+2)%4
        nx = x+dx[direct]
        ny = y+dy[direct]
        #배열의 벽이아니면 후진
        if arr[nx][ny] != 1:
            dfs(nx,ny,(direct+2)%4)


if __name__=='__main__':
    N,M = map(int,s.readline().split())
    r,c,d = map(int,s.readline().split())
    cnt=0
    #북동남서순서
    dx=[-1,0,1,0]
    dy=[0,1,0,-1]
    arr = [list(map(int,s.readline().split())) for _ in range(N)]
    dfs(r,c,d)
    print(cnt)