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

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

14503번: 로봇 청소기

 

내 코드

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

graph= []
n, m =map(int, input().split())
r,c,d = map(int, input().split())
graph : list =[list(map(int,input().split())) for _ in range(n)]
dy :list =[-1,0,1,0]
dx :list = [0,1,0,-1]
def val(ny, nx):
    return 0<=nx<m and 0<=ny <n 

#만약 후진하려면 
#서쪽을 보고 있으면 x +1, y
#동쪽으로 후진은 x -1, y
def bfs(y:int,x:int,d:int):
    res =1
    q = deque()
    q.append((y,x,d))
    graph[y][x] =2
    while q:
        y,x,d =q.popleft()
        for i in range(4):
            d = (d-1)%4
            nx = dx[d]+x
            ny = dy[d]+y
            if val(ny,nx) and not graph[ny][nx]: #청소되지 않은 빈 칸이 있는 경우
                res +=1
                graph[ny][nx] =2
                q.append((ny,nx,d))
                break
            
        else: #사방을 다 청소했을 때
            ny, nx = y-dy[d], x -dx[d] #후진
            if graph[ny][nx] ==1:
                return res
                
            q.append((ny,nx,d))
            
                
print(bfs(r,c,d))

 

코드 리뷰

완전 탐색

짚고 넘어갈 부분이 많다. 나는 BFS, DFS에서 회전하는 문제에 익숙해지기 위해 이 문제를 풀었는데, 그런 부분에서 이 문제는 참 좋은 것 같다. 특히 회전, 후진, 전진이 모두 들어가있는 문제이기 때문에 (공식처럼?) 열심히 풀고, 잘 이해하면 될 것 같다.

 

개념 짚고 넘어가기

1. 방향

개념 부분에서 너무 헷갈렸는데, 여기서부터 정의를 다시 내려야 한다. 우선 우리가 graph를 볼 때 동,서,남,북의 정의부터 다시 할 필요가 있다.

북 동 남 서, 이 방향으로 우리는 정의를 해 줄 것이다. 앞으로 나오는 내용들은 공식처럼 외워두면 정말 편하긴 하다. 반드시 이해하고 넘어가야 다른 문제에서 조건이 바뀌어도 풀 수 있다!

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

이 문제에서 이렇게 정의하는 게 편한 이유는..문제 그대로를 따라가기 위함이다. 문제에서 이렇게 하라고 정의했기 때문이다.

예를 들어 d가 0이라고 했을 때 북, 1은 동... 이렇게 진행된다 하자.(문제 그대로임)

 

d= (d+3)%4 or d= (d-1)%4

그러면 이렇게 진행되는데, d가 0으로 주어지고, 이건 북쪽을 의미한다. 그리고 다음의 d는 3이 된다. (d에 0을 넣었으니까) 그리고 다음의 d는 2가 되고, 그 다음의 d는 1이 된다. 이게 무한 반복된다. 그리고 이 순서는 결국 북, 서, 남, 동의 dy, dx를 가리킨다. 

 

2. 후진할 때

ny, nx = y-dy[d], x -dx[d] #후진
            if graph[ny][nx] ==1:
                return res

후진은 지금 현재 있는 자리의 x, y 좌표에서 -dy[d] 씩 해주면 된다. 이유는 진짜 구현 그대로이기 때문이다. 각 dy[d], dx[d]는 0 아니면 1, -1이다. 만약 -1으로 계산한다면 -1이 되거나 0, 1이 된다. 

북과 남, 동과 서는 각각 x,y좌표가 뒤집혀있는 형태이다. 0,1 이거나 1,0이거나. 이를 하려면 -(-1)을 하면 해결된다.

 

전체 코드 뜯어보기

def bfs(y:int,x:int,d:int):
    res =1
    q = deque()
    q.append((y,x,d))
    graph[y][x] =2
    while q:
        y,x,d =q.popleft()
        for i in range(4):
            d = (d-1)%4
            nx = dx[d]+x
            ny = dy[d]+y
            if val(ny,nx) and not graph[ny][nx]: #청소되지 않은 빈 칸이 있는 경우
                res +=1
                graph[ny][nx] =2
                q.append((ny,nx,d))
                break

함수에 들어가는 인자를 int로 미리 정의해준 것은 시간을 조금이라도 줄이기 위해서이다..처음 낸 코드가 시간 초과가 떠서 어떻게든 줄어보려고 그랬다..ㅎ

우선 이 함수의 결과값을 res로 정했고, 처음 방문한 그래프부터 카운팅하기 때문에 1로 초기화했다. 이후 방문한 graph는 2로 설정했다. bfs로 풀었기 때문에 모든 값들을 q로 넣었다 빼는 것을 반복했고, d는 (d-1)%4 or (d+3)%4로 정의하여 북 서 남 동 순으로 회전할 수 있도록 하였다. 이렇게 해서 q에 넣은 모든 곳을 방문하도록 한다.

 

        else: #사방을 다 청소했을 때
            ny, nx = y-dy[d], x -dx[d] #후진
            if graph[ny][nx] ==1:
                return res
                
            q.append((ny,nx,d))

하지만 위의 코드는 for문(사방)을 모두 방문하는 경우이고, 만약 사방을 다 청소했는데도 청소할 곳이 없다면 후진한다. 후진은 한 칸 뒤로 가면 되고 후진한 곳이 벽인지 확인한다. 만약 벽이라면 더이상 작동하지 않고, 청소를 그만하는 것이니까 break를 걸어준다.

만약 벽이 아니라면 q에 다시 집어넣어서 거기부터 재시작하면 된다.

 

회전 문제를 연습하기에 정말 좋은 문제가 아닐까 싶다.