백준_14503_로봇 청소기(시뮬레이션)(해결 못함)

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

14503번: 로봇 청소기

해결 방법

> 문제에 제시된 방법을 따라가기만 하면 된다.

 

결과

> stack overflow....

> 재귀함수를 너무 많이 불러서 그렇다고 하는데 안부르면 파이썬 재귀 limit에 걸려서 안돌아간다.

> 재귀를 쓰지 않고 풀어봐야겠다.

 

코드

'''

0, 1, 2, 3 == 북 동 남 서

'''

 

import sys

 

sys.setrecursionlimit(10 ** 4)

dx = [-1,0,1,0]

dy = [0,1,0,-1]

 

def check(x,y,board,direct):

    if board[y][x] == 0:

        board[y][x] = 2

    

    for i in range(4):

        if board[y + dy[direct]][x + dx[direct]] == 0:

            direct = direct - 1 if direct - 1 >= 0 else 3

            check(x,y,board,direct)

        else:

            direct = direct - 1 if direct - 1 >= 0 else 3

    

    direct = direct - 2 if direct > 1 else direct + 2

    if board[y - dy[direct]][x - dx[direct]] == 1:

        return print(sum(board,[]).count(2))

    else:

        x -= dx[direct]

        y -= dy[direct]

        check(x,y,board,direct)

 

n,m = map(int, input().split())

now_y, now_x, direct = map(int, input().split())

 

board = []

for i in range(n):

    board.append(list(map(int, input().split())))

 

check(now_x,now_y,board,direct)

코드(재귀x)

> 값이 틀림

'''

0, 1, 2, 3 == 북 동 남 서

'''

 

#북 동 남 서

dx = [0,1,0,-1]

dy = [1,0,-1,0]

 

n,m = map(int, input().split())

y, x, direct = map(int, input().split())

 

board = []

for i in range(n):

    board.append(list(map(int, input().split())))

 

count = 0

while True:

    if count == 4:

        x_prime, y_prime = x - dx[direct], y - dy[direct]

        if board[y_prime][x_prime] == 1:    #2-d 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

            break

        else:   #2-c 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.

            x, y, count = x_prime, y_prime, 0

 

    if board[y][x] == 0:    #1. 현재 위치를 청소한다.

        board[y][x] = 2

    

    direct = direct - 1 if direct - 1 >= 0 else 3

    tmp_x, tmp_y = x + dx[direct], y + dy[direct]

    if board[tmp_y][tmp_x] == 0:    #2-a 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.

        x, y, count = tmp_x, tmp_y, 0

    else:   #2-b 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.

        count += 1

 

print(sum(board,[]).count(2))