[백준]14503번 로봇 청소기(Python)

0. 문제 링크

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

14503번: 로봇 청소기

 

1. 문제 소개

1) 구하고자 하는 것 : 청소한 영역의 개수 구하기

2) 주어진 것

- N X M 직사각형

- r : 북쪽으로부터 떨어진 칸의 개수 / c : 서쪽으로부터 떨어진 칸의 개수, 즉, x, y 좌표가 주어짐

- d : 현재 바라보고 있는 방향이 주어짐. 북(0), 동(1), 남(2), 서(3) 순서대로

- 빈 칸이면 0, 벽이면 1로 주어짐

3) 구현

- 현재 위치가 청소가 되어있지 않으면 청소

- 현재 바라보고 있는 방향에서 왼쪽 회전 -> 전진 -> 청소

- 회전한 위치가 청소가 되어 있으면 다시 왼쪽으로 회전

- 4방향이 모두 청소되어 있거나 벽이면 한 칸 후진

- 4방향이 모두 청소되어 있으면서 벽이면 작동을 멈추고 청소한 영역의 개수 출력

 

2. 입출력

# input
3 3
1 1 0
1 1 1
1 0 1
1 1 1

# output
1

 

3. 코드

# input
n, m = map(int, input().split())
r, c, d = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]

visited = [[0] * m for _ in range(n)]
dx = [-1, 0, 1, 0]                              # 북(0), 동(1), 남(2), 서(3) 순
dy = [0, 1, 0, -1]

def solution(n, m, r, c, d, graph):
    visited[r][c] = 1                                                   # 처음 방문하는 곳 청소
    answer = 1                                                          # 청소 횟수 1로 초기화

    while True:
        # 네 방향 확인
        flag = 0
        for i in range(4):
            nx = r + dx[(d+3)%4]                                        # (d+3)%4 가 왼쪽 방향
            ny = c + dy[(d+3)%4]
            d = (d+3)%4

            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 0:      # 범위 안에 있고, 0이면
                if visited[nx][ny] == 0:                                # 청소 전이면
                    visited[nx][ny] = 1                                 # 청소 처리
                    answer += 1                                         # 청소 횟수 1 증가
                    r, c = nx, ny                                       # 현재 위치 변경
                    flag = 1
                    break

        # 네 방향 모두 청소되어 있으면
        if flag == 0:
            if graph[r-dx[d]][c-dy[d]] == 1:                            # 후진했는데 벽
                return answer
                break
            else:                                                       # 후진했는데 벽이 아님
                r, c = r-dx[d], c-dy[d]

print(solution(n, m, r, c, d, graph))

 

실행 결과

 

4. 회고

- 오랜만에 문제를 풀려니 input부터 헷갈렸다 ;-; input 받는 방식은 숫자 받기 or 그래프 받기 두 가지이기 때문에 확실하게 기억하기!

# 숫자 받기
n, m = map(int, input().split())

# 그래프 받기
graph = [list(map(int, input().split())) for _ in range(n)]

- 항상 헷갈리는게 dx, dy 방향 정하는거 -> 손으로 적어가면서 풀기! 이 문제에서는 단순히 dx, dy를 순서대로 사용하는 게 아니라 (d+3)%4 식으로 왼쪽 방향을 찾도록 수식을 변형하는 게 포인트였음

- 청소한 위치를 체크할 때 graph 리스트 하나만 가지고도 풀 수도 있지만 visited 로 푸는 게 깔끔한 것 같음

- 필요한 경우 flag, return, break 잘 활용하기

 

5. Github

https://github.com/iihye/Algorithm/blob/main/Baekjoon/14503_robot_vacuum.py

GitHub - iihye/Algorithm