[백준] 14503 - 로봇 청소기 [Python(파이썬)]

문제

www.acmicpc.net/problem/14503

14503번: 로봇 청소기

풀이

방향, 전진, 후진에 대한 정보를 딕셔너리에 담아둔다.

여기서 방향이라 함은 왼쪽으로 회전후에 어떠한 방향을 취하게 되는지에 대한 정보를 의미한다.

e.g. 북(0) -> 서(3), 동(1) -> 북(0), 남(2) -> 동(1), 서(3) -> 남(2) 

 

1번부터 진행할 지, 2번부터 진행할 지에 대한 여부는 함수의 매개변수로 전달한다.

4방향을 탐색(2-b)하면서 청소를 할 지(2-a) 결정한다. 4방향 탐색 후에도 청소를 할 공간이 없다면 2-c와 2-d를 판단하고 만약 2-d라면 모든 탐색을 종료한다.

 

아이디어는 어렵지 않으나 구현하는 과정에서 실수가 많았던 문제였다.

 

코드

import sys
sys.setrecursionlimit(10**9)

def dfs(y, x, d, state):
    global cnt
    
    # 1번
    if state: # if state == 1 -> 1번 / if state == 0 -> 2번
        visited[y][x] = 1
        cnt += 1
	
    nd = d
    
	# 2번
    for _ in range(4): # b
        nd = turn[nd]
        ny, nx = y + advance[nd][0], x + advance[nd][1]
        
        if not g[ny][nx] and not visited[ny][nx]: # a
            dfs(ny, nx, nd, 1)
            return
    
    ry, rx = y + regress[d][0], x + regress[d][1]

    if g[ry][rx]: # d
        return
    else:
        dfs(ry, rx, d, 0) # c

    
turn = {0: 3, 1: 0, 2: 1, 3: 2}
advance = {0: [-1, 0], 1: [0, 1], 2: [1, 0], 3: [0, -1]} # [y,x]
regress = {0: [1, 0], 1: [0, -1], 2: [-1, 0], 3: [0, 1]}

n, m = map(int, sys.stdin.readline().split())
r, c, d = map(int, sys.stdin.readline().split())

cnt = 0
g = []
visited = [[0 for _ in range(m)] for _ in range(n)]

for _ in range(n):
    raw = [int(x) for x in sys.stdin.readline().split()]
    g.append(raw)

dfs(r, c, d, 1)
print(cnt)