알고리즘

[백준] 1726 로봇

2025년 09월 22일

#BOJ #Python 3 #알고리즘 #그래프 이론 #그래프 탐색 #너비 우선 탐색

[Gold III] 로봇 - 1726

문제 링크

성능 요약

메모리: 35016 KB, 시간: 64 ms

분류

그래프 이론, 그래프 탐색, 너비 우선 탐색

문제 설명

많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 다음과 같이 두 가지이다.

명령 1. Go k: k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다. 명령 2. Turn dir: dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다.

공장 내 궤도가 설치되어 있는 상태가 아래와 같이 0과 1로 이루어진 직사각형 모양으로 로봇에게 입력된다. 0은 궤도가 깔려 있어 로봇이 갈 수 있는 지점이고, 1은 궤도가 없어 로봇이 갈 수 없는 지점이다. 로봇이 (4, 2) 지점에서 남쪽을 향하고 있을 때, 이 로봇을 (2, 4) 지점에서 동쪽으로 향하도록 이동시키는 것은 아래와 같이 9번의 명령으로 가능하다.

로봇의 현재 위치와 바라보는 방향이 주어졌을 때, 로봇을 원하는 위치로 이동시키고, 원하는 방향으로 바라보도록 하는데 최소 몇 번의 명령이 필요한지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공장 내 궤도 설치 상태를 나타내는 직사각형의 세로 길이 M과 가로 길이 N이 빈칸을 사이에 두고 주어진다. 이때 M과 N은 둘 다 100이하의 자연수이다. 이어 M줄에 걸쳐 한 줄에 N개씩 각 지점의 궤도 설치 상태를 나타내는 숫자 0 또는 1이 빈칸을 사이에 두고 주어진다. 다음 줄에는 로봇의 출발 지점의 위치 (행과 열의 번호)와 바라보는 방향이 빈칸을 사이에 두고 주어진다. 마지막 줄에는 로봇의 도착 지점의 위치 (행과 열의 번호)와 바라보는 방향이 빈칸을 사이에 두고 주어진다. 방향은 동쪽이 1, 서쪽이 2, 남쪽이 3, 북쪽이 4로 주어진다. 출발지점에서 도착지점까지는 항상 이동이 가능하다.

출력

첫째 줄에 로봇을 도착 지점에 원하는 방향으로 이동시키는데 필요한 최소 명령 횟수를 출력한다.

문제 풀이

문제 분석

이 문제는 M x N 크기의 공장 궤도 정보와 로봇의 시작 위치, 시작 방향, 도착 위치, 도착 방향이 주어졌을 때, 로봇을 시작 위치에서 도착 위치로 이동시키고 원하는 방향으로 바라보게 하는 최소 명령 횟수를 구하는 문제입니다. 로봇은 'Go k' (k는 1, 2, 3) 명령으로 현재 바라보는 방향으로 k칸 만큼 움직이거나, 'Turn dir' (dir은 left 또는 right) 명령으로 왼쪽 또는 오른쪽으로 90도 회전할 수 있습니다. 궤도가 없는 곳(1)으로는 이동할 수 없습니다.

접근 방법

이 문제는 BFS(너비 우선 탐색) 알고리즘을 사용하여 해결할 수 있습니다. BFS는 시작 지점에서 가장 가까운 노드부터 탐색하므로, 최소 명령 횟수를 찾는 데 적합합니다. 각 노드는 로봇의 위치 (x, y)와 방향을 나타냅니다. 탐색 과정에서 로봇이 이동할 수 있는 모든 위치와 방향을 큐에 넣고, 방문 여부를 체크하여 중복 방문을 방지합니다.

구현 설명

1. 초기화

directions: 로봇의 방향(동, 서, 남, 북)에 따른 좌표 변화를 나타내는 리스트입니다.
BFS() 함수: BFS 알고리즘을 구현하는 함수입니다.
queue: BFS 탐색을 위한 큐이며, 시작 위치와 방향을 넣어 초기화합니다.
visited: 방문 여부를 저장하는 3차원 배열입니다. visited[x][y][dir]은 (x, y) 위치에서 dir 방향으로 방문했는지 여부를 나타냅니다. 시작 위치를 방문 처리합니다.

2. BFS 탐색

while queue: 큐가 빌 때까지 반복합니다.
for i in range(len(queue)): 현재 큐에 있는 모든 노드에 대해 탐색을 수행합니다. 큐에 들어있는 노드들을 한번에 처리하여 level을 구분합니다.
x, y, dir = queue.popleft(): 큐에서 노드를 꺼내 현재 위치와 방향을 가져옵니다.
if x == end_x-1 and y == end_y-1 and dir == end_dir-1: 현재 위치와 방향이 목표 위치와 방향과 같으면, 현재까지의 명령 횟수(cnt)를 반환합니다.

3. 이동 및 회전

이동: for idx in range(1, 4): 현재 방향으로 1칸, 2칸, 3칸 이동해봅니다.
- sx, sy = x + dx * idx, y + dy * idx: 이동할 위치를 계산합니다.
- if 0 <= sx < n and 0 <= sy < m and board[sx][sy] == 0: 이동할 위치가 공장 범위 내에 있고 궤도가 깔려 있다면 (0),
  - if not visited[sx][sy][dir]: 아직 방문하지 않았다면, 큐에 추가하고 방문 처리합니다.
- else: break: 궤도가 없거나 범위를 벗어나면 더 이상 이동할 수 없으므로 반복문을 종료합니다.
회전:
- right_turn, left_turn: 오른쪽, 왼쪽으로 회전했을 때의 방향을 나타내는 딕셔너리입니다.
- 회전한 방향에 대해 방문하지 않았다면, 큐에 추가하고 방문 처리합니다.

4. 명령 횟수 증가

cnt += 1: 한 레벨의 탐색이 끝나면 명령 횟수를 1 증가시킵니다. 이는 'Go k' 명령 또는 'Turn dir' 명령을 한 번 수행했음을 의미합니다.

⏱복잡도 분석

시간 복잡도: O(M * N * 4 * 3). M x N은 공장의 크기이고, 4는 가능한 방향의 수입니다. 각 위치에서 최대 3번 이동할 수 있으므로 이동에 대한 복잡도는 *3입니다. 따라서 최악의 경우 모든 위치와 방향을 탐색해야 하므로 시간 복잡도는 O(M * N)입니다.
공간 복잡도: O(M * N * 4). visited 배열은 M x N 크기의 공장 궤도에 대해 각 방향별로 방문 여부를 저장하므로 공간 복잡도는 O(M * N * 4)입니다. 큐 또한 최악의 경우 모든 노드를 저장할 수 있으므로 공간 복잡도는 O(M * N * 4)입니다.

핵심 포인트

BFS 활용: 최단 거리를 찾는 문제이므로 BFS를 사용하는 것이 핵심입니다.
3차원 방문 배열: 위치(x, y)뿐만 아니라 방향까지 고려하여 방문 여부를 저장해야 합니다. 그렇지 않으면 무한 루프에 빠질 수 있습니다.
이동 거리 제한: 'Go k' 명령은 최대 3칸까지 이동할 수 있으므로, 이동 가능한 거리를 반복문으로 처리해야 합니다. 이동 중 궤도가 끊기면 즉시 중단해야 합니다.

풀이 코드

import sys
from collections import deque

input = sys.stdin.readline

#dir 0,1,2,3 동 서 남 북
directions = [(0,1),(0,-1),(1,0),(-1,0)]

def BFS():
    queue = deque()
    queue.append((start_x-1,start_y-1,start_dir-1))
    visited = [[[False] * 4 for i in range(m)] for i in range(n)]
    visited[start_x-1][start_y-1][start_dir-1] = True
    cnt = 0
    while queue:
        for i in range(len(queue)):
            x,y,dir = queue.popleft()

            if x == end_x-1 and y == end_y-1 and dir == end_dir-1:
                return cnt
            
            dx,dy = directions[dir]
            for idx in range(1,4):
                sx,sy = x+dx*idx,y+dy*idx
                if 0<=sx<n and 0<=sy<m and board[sx][sy] == 0:
                    if not visited[sx][sy][dir]:
                        queue.append((sx,sy,dir))
                        visited[sx][sy][dir] = True

                else:
                    break

            right_turn = {0:2, 2:1, 1:3, 3:0}
            left_turn  = {0:3, 3:1, 1:2, 2:0}

            r = right_turn[dir]
            if not visited[x][y][r]:
                queue.append((x, y, r))
                visited[x][y][r] = True

            l = left_turn[dir]
            if not visited[x][y][l]:
                queue.append((x, y, l))
                visited[x][y][l] = True

        cnt += 1

    return -1

n,m= map(int,input().split())
board = []
for i in range(n):
    board.append(list(map(int, input().split())))

start_x,start_y,start_dir = map(int, input().split())
end_x,end_y,end_dir = map(int, input().split())

print(BFS())

댓글을 불러오는 중...