1726. 로봇 - BFS, 구현, 시뮬레이션

사용한 알고리즘 및 자료구조

1. BFS
2. 큐
3. 델타를 이용한 2차원 좌표 탐색

접근 방식

로봇이 한 턴 내에 할 수 있는 동작은 세 가지다.

1. 1~3칸 전진.
2. 좌로 회전.
3. 우로 회전.

로봇의 상태를 que에서 받은 뒤, 위 세 가지 연산을 전부 처리한다. 

로봇의 위치와 로봇이 바라보는 방향 모두를 정확히 기록해야 하기에, 3차원 방문 여부 리스트를 활용했다. 

 

문제 특이사항

일반적으로 2차원 좌표 탐색 문제에서, '방향을 돌리는' 연산은 나머지 연산을 통해 쉽게 구현할 수 있다.

(나누기를 활용해 2차원 좌표 탐색에 활용하는 문제 샘플을 곧 업로드 하겠습니다.)

 

하지만 이 문제는 '동쪽이 1, 서쪽이 2, 남쪽이 3, 북쪽이 4' 라고 명시하고 있다. 따라서 좌표를 입력받을 때 적당히 변형하거나, 회전하는 함수를 직접 구현해야 한다. 

 

어려웠던 점

9월 중순부터 풀기 시작했다. 당시에는 3차원 visited 리스트를 활용할 생각을 하지 못했다. 일반적인 BFS를 활용해 '목표 지점'까지 가장 먼저 도착하는 경우를 계산한 뒤, 그 상태에서 몇 번 회전하면 되는지를 계산해서 답을 출력했다. 

 

17070. 파이프 옮기기를 풀고 나서야 내 풀이가 어느 부분에서 잘못되었는지 확인할 수 있었다. 

 

느낀 점 

1. 변수명을 정말 잘 설정해야 한다. 

처음으로 디버깅 무간지옥에 빠졌던 문제다. 몇 시간동안 같은 코드를 잡고 있다보면 어느새 나도 내 코드의 원래 의도가 무엇이었는지 확인하기가 힘들었다. 처음부터 변수명을 잘 설정해두면 '내 의도가 내 코드에 알맞게 전달되었는지'를 비교적 쉽게 확인할 수 있다. 내 코드와 input, output값의 관계만 잘 확인하면 되는 것이다. 

 

2. 3차원 vistied 리스트의 활용. 

2차원 좌표평면에서 무언가를 구현한다고 해서 방문 여부 배열까지 2차원 리스트여야 할 필요는 없다. 딕셔너리 등을 활용하는 방법도 존재할 것이다. 

 

풀었을 당시의 백준 티어 

2021-10-03, 골드 2

 

실행시간, 메모리, 언어

124ms, 32132kb, Python3

 

from collections import deque
from sys import stdin


def turn_left(direction):
    """
    :param direction: current direction of robot
    :return: returns direction turned left
    """
    turn_dir = (3, 2, 0, 1)
    return turn_dir[direction]


def turn_right(direction):
    """
    :param direction: current direction of robot
    :return: returns direction turned right.
    """
    turn_dir = (2, 3, 1, 0)
    return turn_dir[direction]


# 1. 입력
# 1-1. 2차원 배열 정보 입력
BORDER_Y, BORDER_X = map(int, stdin.readline().split())  # BORDER_Y: 행의 갯수 BORDER_X: 열의 갯수
WALL = [list(map(int, stdin.readline().split())) for _ in range(BORDER_Y)]  # wall.

# 1-2. 로봇의 시작지점 입력받음.
# 문제 조건상 '첫 번째 점'을 (1, 1)로 계산하므로, 연산 편의를 위해 값을 수정.
START_Y, START_X, START_D = map(int, stdin.readline().split())
START_Y -= 1
START_X -= 1
START_D -= 1

# 1-3. 목표지점. 입력 받음.
# 문제 조건상 '첫 번째 점'을 (1, 1)로 계산하므로, 연산 편의를 위해 값을 수정.
GOAL_Y, GOAL_X, GOAL_D = map(int, stdin.readline().split())
GOAL_Y -= 1
GOAL_X -= 1
GOAL_D -= 1

# 2. 선언
# 2-1. visited 배열 선언.
# visited 배열 선언.
# 어떤 방향에서 오는지 정보도 함께 기입해야하므로
# 3차원 배열로 선언. [0, 0, 0, 0]은 각각 방향이 동쪽인 상태, 서쪽
visited = [list([0] * 4 for _ in range(BORDER_X)) for _ in range(BORDER_Y)]
visited[START_Y][START_X][START_D] = 1

DX = (1, -1, 0, 0)  # 0 동 1 서 2 남 3 북
DY = (0, 0, 1, -1)  # 0 동 1 서 2 남 3 북

# 2-2. 큐 선언
moves_que = deque()  # 움직임들을 선입선출할 큐를 선언하고
moves_que.append((START_Y, START_X, START_D))  # 큐에 시작지점을 입력.

# 3. 연산
while True:  # 문제 조건상 언제나 목표지점에 도착할 수 있다. 따라서 큐가 True 인지 확인해 줄 필요가 없다.

    # 3-1. 종료 조건.
    if visited[GOAL_Y][GOAL_X][GOAL_D]:  # 만약에 목표 지점에 도착했다면
        break  # 시행을 종료한다.

    # 3-2. 움직임 연산
    # 현재 살펴볼 지점의 Y, X, Direction 좌표.
    current_y, current_x, current_d = moves_que.popleft()

    # 3-2-1. 전진 연산
    next_y = current_y  # 다음 y좌표
    next_x = current_x  # 다음 x좌표

    for forward_moves in range(3):  # 3회 전진
        next_y += DY[current_d]  # 델타를 이용한...
        next_x += DX[current_d]

        # 1) 전진 종료 조건
        if next_y < 0 or next_y >= BORDER_Y or\
            next_x < 0 or next_x >= BORDER_X or\
            WALL[next_y][next_x]:  # 만약 길이 막혔거나 인덱스 오버플로우가 일어난다면
            break  # 탐색 종료

        # 2) 전진 비 갱신 조건
        if visited[next_y][next_x][current_d]:  # 만약 이미 방문한 지점이라면
            continue  # 무시 후 다음 좌표 확인.

        # 3) 전진
        visited[next_y][next_x][current_d] = visited[current_y][current_x][current_d] + 1  # 몇 번째에 방문했는지 기록 후
        moves_que.append((next_y, next_x, current_d))  # 움직임을 큐에 다시 삽입.

    # 3-2-2. 회전 연산
    left_turn = turn_left(current_d)  # 현재 지점에서 왼쪽으로 회전한 값
    right_turn = turn_right(current_d)  # 현재 지점에서 오른쪽으로 회전했을 때의 방향값.

    for next_dir in (left_turn, right_turn):  # 모든 회전 움직임에 대해

        # 1) 회전 갱신 조건
        if not visited[current_y][current_x][next_dir]:

            # 회전 후 visited 갱신

            visited[current_y][current_x][next_dir] \
                = visited[current_y][current_x][current_d] + 1

            # 다음 움직임을 큐에 삽입.
            moves_que.append((current_y, current_x, next_dir))

# 4. 출력
print(visited[GOAL_Y][GOAL_X][GOAL_D] - 1)