[Python] 백준 14503 : 로봇 청소기

오늘은 구현문제 중 하나인 로봇청소기를 풀어보았다.

 

 

 

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

14503번: 로봇 청소기

 

문제를 간략히 요약하면

1. 방의 크기가 N, M 크기로 입력 받음

2. 초기에 로봇청소기 위치와 방향을 입력 받음

3. 방에 기본값을 입력 받음

4. 0은 청소해야 할 곳, 1은 벽

5. 청소를 진행할 때 청소할 수 있는 구역의 합을 출력하라.

 

풀이

1. 입력을 다 받아준다.

2. deque에 초기값을 넣어준다. (x, y, d) 위치 / 방향

3. bfs를 돌려 값을 확인한다.

4. 내가 보고 있는 방향에서 반시계 방향으로 회전 후 청소하지 않은 방이면 진입하고 청소 후 visited에 True 표시

5. 4 방향 모두 청소가 된 곳이라면 한칸 후진하여 다시 탐색

6. 후진한 부분이 벽이라면 기기 종료

 

 

from collections import deque

N, M = map(int, input().split())    
r, c, d = map(int, input().split())
B = [list(map(int, input().split())) for _ in range(N)]
visited = [[False] * M for _ in range(N)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
cnt = 0


def bfs(x, y, d):
    global cnt
    q = deque()
    q.append((x, y))
    visited[x][y] = True
    cnt += 1
    while q:
        x, y = q.popleft()
        turn = 0
        for i in range(4):
            d = (d + 3) % 4
            nx, ny = x + dx[d], y + dy[d]
            
            if 0 <= nx < N and 0 <= ny < M and not B[nx][ny]:
                if not visited[nx][ny]:
                    visited[nx][ny] = True
                    q.append((nx, ny))
                    turn = 1
                    cnt += 1
                    break

        if turn == 0:
            bx, by = x - dx[d], y - dy[d]
            if B[bx][by] == 1:
                print(cnt)
                break
            else:
                q.append((bx, by))

bfs(r, c, d)

 

 

시간은 좀 오래걸렸지만 관련 문제를 많이 풀어봐야겠다.