[BOJ] 14503 로봇청소기 - python

문제 링크 (opens new window)

탐색, 구현 문제

문제 요약

NxM 맵이 주어지고, 시작점(로봇)의 위치가 주어질때, 탐색 가능한 칸의 개수를 구해라. 단, 주어진 규칙에 의해서 탐색할수있다.

문제 접근

처음에는 이동 규칙 무시하고 DFS 돌려도 될거같은데하고 구현해봤으나, 예제2랑 다른 답이 나왔다. 그래서 규칙을 그대로 반영하면서 탐색하도록 구현하였다.

1. A, B 로직 (최대 4번 반복한다) (A) 로봇 청소기 방향을 돌리면서 만일 왼쪽을 청소할수있다면, dfs(왼쪽위치, 왼쪽방향) 을 호출한다. 호출이 끝나면 현재 dfs 를 종료한다. (B) 청소할수없다면 청소기의 방향을 왼쪽 방향으로 바꿔준다. 1로직으로 돌아간다.

2. 1로직을 4번 반복했는데도 현재 dfs 가 끝나지 않았다는 것은 청소할칸이 없다는 것이다.

3. C 로직. 청소기를 후진하는 위치로 dfs 호출한다. 호출이 끝나면 현재 dfs 를 종료

4. D 로직. 종료

소스 코드

import sys
input = sys.stdin.readline

def dfs(r, c, d):
    if not visited[r][c]:
        global ans
        visited[r][c] = 1
        ans += 1
    
    # a, b logic
    for _ in range(4):
        d = left[d]
        lr, lc = r+dirs[d][0], c+dirs[d][1]
        if board[lr][lc] != 1 and not visited[lr][lc]:
            dfs(lr, lc, d)
            return

    # c logic
    bd = (-1*d[0], -1*d[1])
    br, bc = r+dirs[bd][0], c+dirs[bd][1]
    if board[br][bc] != 1:
        dfs(br, bc, d)
        return

    # d logic
    return
    

ans = 0
N, M = map(int, input().split())

# robot position
rr, rc, d = map(int, input().split())
rr, rc = rr+1, rc+1

board = [[1]*(M+2) for r in range(N+2)]
visited = [[0]*(M+2) for r in range(N+2)]

dirs = [(-1, 0), (0, 1), (1, 0),(0,-1)]
left = {0: 3, 1: 0, 2: 1, 3: 2}
# up, right, down, left

for r in range(1, N+1):
    s = list(map(int, input().split()))
    for c in range(1,M+1):
        board[r][c] = s[c-1]

dfs(rr, rc, d)
print(ans)

• board[N+2][M+2] : 테두리 부분은 벽으로 채워넣어서, 탐색하면서 범위를 벗어나는 경우를 체크하지않아도 되도록 하였다.
• dirs[4] : [up, right, down, left], (dr, dc)꼴의 방향벡터 배열
• left[d] : d 방향일때의 왼쪽 방향