[테스트케이스 추가] 백준 14503번: 로봇 청소기 , python 파이썬

1. 문제

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

14503번: 로봇 청소기

 

 

2. 풀이

시뮬레이션

주의할 점은 뒤로 후진 할 때 벽을 마주치면 바로 리턴해야하는 것이다.

모든 곳을 돌면 안되고 위의 케이스가 있는 지 확인해야한다.

 

 

3. 구현

import sys
sys.stdin = open('input.txt')
sys.setrecursionlimit(10**8)
dx=[0,1,0,-1]
dy=[-1,0,1,0]

n,m = map(int, sys.stdin.readline().strip().split())
startR, startC, di = map(int, sys.stdin.readline().strip().split())

g=[]
for i in range(n):
    g.append(list(map(int, sys.stdin.readline().strip().split())))
visit = [[0 for _ in range(m)] for __ in range(n)]

def valid(r,c):
    return r>=0 and c>=0 and r<n and c<m

circle=[[3,2,1,0], [0,3,2,1], [1,0,3,2], [2,1,0,3]]
back_dir = {0:2, 1:3, 2:0, 3:1}
max_val=0

return_flag=False
def dfs(r,c,d):
    global return_flag
    nextDir = -1
    cnt=0
    
    if return_flag==True:
        return
    for i in circle[d]:
        nextDir = i
        if return_flag==True:
            break
        nextR = r+dy[i]
        nextC = c+dx[i]
        if not valid(nextR, nextC):
            cnt+=1
            if cnt==4:
                
                nextR = r+dx[back_dir[d]]
                nextC = c+dy[back_dir[d]]
                if g[nextR][nextC]==1:
                    return_flag=True
                    return
                else:
                    dfs(nextR,nextC,d)
            continue
        if g[nextR][nextC]==1:
            cnt+=1
            if cnt==4:
                nextR = r+dy[back_dir[d]]
                nextC = c+dx[back_dir[d]]
                if g[nextR][nextC]==1:
                    return_flag=True
                    return
                else:
                    dfs(nextR,nextC,d)
            continue
        if visit[nextR][nextC]!=0:
            cnt+=1
            if cnt==4:
                nextR = r+dy[back_dir[d]]
                nextC = c+dx[back_dir[d]]
                if g[nextR][nextC]==1:
                    return_flag=True
                    return
                else:
                    dfs(nextR,nextC,d)
            continue
        visit[nextR][nextC]=visit[r][c]+1
        dfs(nextR,nextC,nextDir)
    return

visit[startR][startC]=1
dfs(startR, startC, di)
# print(visit)

answer=0
for i in range(n):
    for j in range(m):
        if visit[i][j]!=0:
            answer+=1
print(answer)

 

 

4. 질문반례 및 테스트케이스 추가

 

https://www.acmicpc.net/board/view/67972

6 6
2 1 3
1 1 1 1 1 1
1 0 0 0 0 1
1 0 1 1 1 1
1 0 1 1 1 1
1 0 1 1 1 1
1 1 1 1 1 1

답: 7

 

 

https://www.acmicpc.net/board/view/34953

6 7
2 1 0
1 1 1 1 1 1 1
1 0 0 0 0 0 1
1 0 1 0 1 0 1
1 1 0 1 1 0 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1

답: 15

 

 

8 10
0 0 0
0 1 1 1 0 1 0 0 0 1
0 0 0 0 0 1 0 0 0 1
0 1 0 0 1 0 1 0 0 0
1 1 1 0 1 1 1 0 0 1
1 0 1 1 0 1 0 0 0 1
1 0 0 0 0 1 1 0 0 0
0 0 0 1 1 1 0 1 0 1
0 1 1 1 1 0 1 0 0 0

답: 9

 

 

12 9
0 0 0
0 0 0 1 1 0 0 0 1
0 0 1 0 0 0 0 1 1
1 0 1 0 0 0 0 0 1
1 0 0 0 1 1 0 1 1
0 0 1 1 1 0 0 0 1
0 1 1 1 1 0 1 0 1
1 0 1 1 1 0 0 1 1
0 0 0 0 1 0 0 1 1
1 0 0 0 0 0 0 1 1
1 0 1 1 0 1 1 1 0
1 1 0 1 1 1 0 1 0
1 0 1 1 1 1 1 0 0

답: 5

 

 

5 5
0 0 0
0 1 0 1 0
0 1 0 1 1
0 0 0 1 0
0 1 1 1 0
1 1 0 1 0

답: 7