백준 14503 로봇 청소기 (python)

문제

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

나의 접근법

저는 이 문제를 처음에는 BFS로 빠르게 풀려고 했습니다. 그런데 BFS는 경우 모든 장소를 탐색하지만 이 문제는 로봇청소기의 규칙대로 움직이기 때문에 연결된 모든 장소를 탐색하는 기존의 BFS 와는 조금 다른 방법으로 풀어야합니다.

이 문제를 풀면서 추가로 고려해야 할 점들이 조금 있었습니다.

사실 BFS라기 보다는 구현, 시뮬레이션, 완전탐색 문제에 가깝습니다.

 

1. 평범한 BFS 문제는 처음 방문하면 방문 표시를 해서 단 한번만 방문을 하게 하지만 이 문제는 뒤로가기를 하기 위해 방문했던 곳을 다시 방문할 수 있게 해야합니다.

 

2. 회전의 순서가 방향 순서와 다릅니다.

• 방향 순서 (북쪽기준, 시계방향) : [북, 동, 남, 서]
• 회전 순서 (북쪽기준, 반시계 방향) : [북, 서, 남, 동]
• 방향 순서가 다르기 때문에 다음 방향을 체크하는 코드를 살짝 다르게 작성해야합니다.

저는 방문한 칸의 개수를 2로 시작했습니다. 이유는 디버그 하면서 1부터 시작하면 벽과 겹칠수 있다고 생각했기 때문에 2부터 시작하고 로봇청소기의 탐색 위치를 cnt로 MAP에 넣어주며 값의 변화를 확인했습니다. 그 후 마지막에는 cnt-1을 출력하여 1부터 시작하게 만들었습니다.

 

그리고 뒤로 갈 수 있는지 확인하는 함수 checkGoBack 과 와 왼쪽으로 갈 수 있는지 확인하는 함수 checkLeft 를 작성하여 가독성을 높여보았습니다.

 

정답 코드

import sys
from collections import deque
def checkLeft(nx, ny):
    if MAP[nx][ny] == 0:
        if 1 <= nx < N - 1 and 1 <= ny < M - 1:
            return True
    else:
        return False

def checkGoBack(x, y, d, MAP):
    nd = (d + 2) % 4 # 뒤로 가기
    nx, ny = x + dx[nd], y + dy[nd]
    if MAP[nx][ny] == 1:
        return False
    return nx, ny

def BFS(r, c, direction, MAP):
    cnt = 2
    q = deque()
    q.append([r, c, direction])

    while q:
        x, y, d = q.popleft()
        MAP[x][y] = cnt
        nd = d
        for i in range(4):
            nd -= 1
            if nd == -1: nd = 3
            nx, ny = x + dx[nd], y + dy[nd]
            if checkLeft(nx, ny):
                 cnt += 1
                 q.append((nx, ny, nd))
                 break

            # 4방향 모두 확인했는데 청소할 공간이 없는 경우
            elif i == 3:
                result = checkGoBack(x, y, d, MAP)
                if not result:
                    return cnt - 1

                else:
                    nx, ny = result
                    q.append((nx, ny, d))  # 방향은 그대로

N, M = map(int, sys.stdin.readline().split())
r, c, d = map(int, sys.stdin.readline().split())
MAP = []
for i in range(N):
    MAP.append(list(map(int, sys.stdin.readline().split())))

#회전:북 > 서 > 남 > 동 = 0 > 3 > 2 > 1
# 북동남서 방향으로
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

print(BFS(r, c, d, MAP))

백준 결과

오 실버 문제인줄 알았는데 골드였네요. 엄청 어려운건 아니었지만 그래도 문제를 꼼꼼하고 방향 설정을 잘 해줘야 한번에 맞을 수 있을 것 같습니다. 

 

후기 및 돌아보기

최종 코드만 보면 단순하고 쉬워 보이는데 실제 처음부터 풀어보니 위에서 고려하지 못한 문제들로 인해 계속 답이 다르게 나왔습니다.

단순 BFS로 안되고 그 다음 회전을 시켰지만 회전 순서를 북, 동, 남, 서 (시계방향)으로 설정해서 삽질을 오래 했습니다.

또한 nd 변수를 설정을 for 밖에서 설정하지 않고 for문 안에서 설정하는 바람에 코드가 딴길로 새었습니다.

또 이 한 문제를 풀기 위해 오랜 시간이 걸렸습니다.

지금 단계는 문제를 보면 "어떤 방법으로 어떻게 틀을 짜볼까?" 라는 생각을 하는 수준까지는 온 것 같으나 그 안의 디테일한 변수나 사소한 설정에서 자꾸 시간을 까먹는 것 같습니다.

하지만 이러한 과정을 겪어 봐야 나중에 완벽하고 클린한 코드를 작성할 수 있다고 생각합니다.

다음에는 더 빨리 코드를 작성해서 답까지 맞았으면 좋겠습니다. 그날이 오기 전까지 계속 달려보겠습니다.