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

문제

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

14503번: 로봇 청소기

풀이

로봇청소기가 0으로 연결된 영역을 전부 청소할 것이라고 생각해서 BFS로 풀려고 했지만,

2-c와 2-d 조건에 의해 0으로 연결된 영역이라고 하더라도 로봇 청소기가 청소하지 않은 영역이 생기게 되어 결국 구현 문제라는 것을 깨달았습니다.

문제에서 주어진 2번 예제에서 로봇청소기가 청소하고 나면 matrix[4][8]과 matrix[6][6] 두 영역이 청소를 안하고 남게 됩니다.

 

clean() 함수를 선언하고 로봇 청소기가 청소를 하고 나면 matrix의 값은 0에서 2로 수정하고 clean_cnt가 1 만큼 더해지도록 구현했습니다.

direction 0, 1, 2, 3이 각각 북, 동, 남, 서를 의미하므로 해당 index에 맞게 dy, dx를 선언합니다.

dy = [-1, 0, 1, 0]  # 북, 동, 남, 서
dx = [0, 1, 0, -1]

2 조건에서 로봇청소기는 현재 방향을 기준으로 왼쪽 방향으로 회전한다고 했는데, (direction + 3) % 4 식을 통해 반시계 방향으로 회전할 수 있습니다.

2-c 조건에서 후진하려면 현재 방향의 반대 방향을 찾아야 하는데, (direction + 2) % 4 식으로 구현합니다.

2-d 조건에 의해 더이상 후진할 곳이 없으면 작동이 종료됩니다.

코드

import sys


def clean(r, c, d):
    global clean_cnt, matrix
    if matrix[r][c] == 0:
        clean_cnt += 1
        matrix[r][c] = 2
    for _ in range(4):
        nd = (d + 3) % 4
        nr = r + dy[nd]
        nc = c + dx[nd]
        if 0 <= nr < n and 0 <= nc < m:
            if matrix[nr][nc] == 0:
                clean(nr, nc, nd)
                return
        d = nd
    nd = (d + 2) % 4
    nr = r + dy[nd]
    nc = c + dx[nd]
    if matrix[nr][nc] == 1:
        return
    clean(nr, nc, d)


n, m = map(int, sys.stdin.readline().rstrip().split())
s_r, s_c, s_d = map(int, sys.stdin.readline().rstrip().split())
matrix = []
for _ in range(n):
    matrix.append(list(map(int, sys.stdin.readline().rstrip().split())))
clean_cnt = 0

dy = [-1, 0, 1, 0]  # 북, 동, 남, 서
dx = [0, 1, 0, -1]

clean(s_r, s_c, s_d)
print(clean_cnt)