[백준🥇5] #14503 로봇 청소기 (Python)

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

[14503번: 로봇 청소기

첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$  둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽

www.acmicpc.net](https://www.acmicpc.net/problem/14503)

예제 입력 1

3 3
1 1 0
1 1 1
1 0 1
1 1 1

예제 출력 1

1

예제 입력 2

11 10
7 4 0
1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 1 1 1 1 0 1
1 0 0 1 1 0 0 0 0 1
1 0 1 1 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1

예제 출력 2

57

✔️ Code

import sys
from collections import deque
input = sys.stdin.readline

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 for _ in range(m)] for _ in range(n)]
cnt = 0

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def bfs(i, j, d):
    global cnt
    queue = deque()
    queue.append((i, j)) # 로봇 위치
    visited[i][j] = 1
    cnt += 1

    while queue:
        x, y = queue.popleft()
        flag = 0

        for _ in range(4): # 반시계 방향으로 돌려감
            d = (d + 3) % 4
            nx = x + dx[d]
            ny = y + dy[d]

            if 0 <= nx < n and 0 <= ny < m and not graph[nx][ny]: 
                if not visited[nx][ny]:
                    visited[nx][ny] = 1  
                    queue.append((nx, ny))
                    cnt += 1
                    flag = 1 # 반시계 방향으로 돌아갔을 때 빈칸이 있다는 것을 의미
                    break


        if flag == 0: # 청소할 곳이 없다면 후진
            if graph[x - dx[d]][y - dy[d]] != 1:
                queue.append((x - dx[d], y - dy[d]))

            else:
                print(cnt)
                break

bfs(r, c, d)

✏️ Comment

bfs로 풀었다. 사실 구현하다가 잘 안풀려서 구글링을 참고했다.. ㅎㅎ 오늘 저녁에 다시 풀어보는 걸로.

반시계 방향 구하기 : (d+3)%4
후진 위치 구하기 : graph[x-dx[d]][y-dy[d]]

이 두가지가 해당 문제에서 가장 중요한 아이디어(?)라고 생각한다..

아, 추가로 초기에는 빈칸을 청소하고 나면 graph[nx][ny] = 1로 바꿔주었었다. 그런데 답이 계속 틀리게 나와서 다시 생각해본 후 깨달았따... 1은 벽을 의미한다는 것을.. 그래서 visited 배열을 두고 방문여부를 따로 체크해주는 방식으로 바꾸었다.