[백준] 1726 : 로봇 / python

1. 문제 설명

1726번: 로봇

문제

많은 공장에서 로봇이 이용되고 있다.

우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며,

움직이는 방향은 동, 서, 남, 북 가운데 하나이다.

로봇의 이동을 제어하는 명령어는 다음과 같이 두 가지이다.

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

로봇의 현재 위치와 바라보는 방향이 주어졌을 때,

로봇을 원하는 위치로 이동시키고, 원하는 방향으로 바라보도록 하는데

최소 몇 번의 명령이 필요한지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 공장 내 궤도 설치 상태를 나타내는

직사각형의 세로 길이 M과 가로 길이 N이 빈칸을 사이에 두고 주어진다.

이때 M과 N은 둘 다 100이하의 자연수이다.

M줄에 걸쳐 한 줄에 N개씩 각 지점의 궤도 설치 상태를 나타내는 숫자 0 또는 1이 빈칸을 사이에 두고 주어진다.

다음 줄에는 로봇의 출발 지점의 위치 (행과 열의 번호)와 바라보는 방향이 빈칸을 사이에 두고 주어진다.

마지막 줄에는 로봇의 도착 지점의 위치 (행과 열의 번호)와 바라보는 방향이 빈칸을 사이에 두고 주어진다.

방향은 동쪽이 1, 서쪽이 2, 남쪽이 3, 북쪽이 4로 주어진다. 출발지점에서 도착지점까지는 항상 이동이 가능하다.

 

출력

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

 

2. 1차 풀이하면서 막혔던 점과 고민

• 처음 문제를 풀기 위해서 로봇이 도착지로 갈 수 있는 모든 경우를 다 따져주어 최소 명령횟수를 구해주려고 했다. 백트레킹으로 접근해보려고 했다.
• 백트레킹으로 접근한다면, DFS 탐색하면서 count할 때, 한쪽방향으로 K개 연속을 어떻게 처리해줄 수 있을까? 라는 생각이 들었는데 step1 가는 경우, step2 가는 경우, step3 가는 경우도 다 따져주면 된다고 생각했다.
• 그런데 문제가 있다. 백트레킹 할 경우 N이 100이므로 가지치기 해주어야 하는데 가지치기를 해주어도 시간 초과가 날 수 있다는 문제점이 발생한다.

 

3. 2차 풀이 전 계획과 생각

🤔 모든 경우를 따져야 할 것 같은데 백트레킹 하기에는 N이 크다. 어떻게 시간 복잡도를 줄여줄 수 있을까?

최소 명령 횟수를 구해주어야 하기 때문에 그래프로 정의하고 edge와 vertex의 정의를 잘하여 최소의 경로를 갈 수 있도록 해주어야 겠다는 생각이 들었다. 로봇이 이동하는 격자를 그래프로 정의하고 BFS 탐색해보자.

 

 

4. 2차 풀이

from collections import deque

import sys
input = sys.stdin.readline

# 동 서 남 북
dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]

rotate_all_dir = ((2, 3), (2, 3), (0, 1), (0, 1))

def in_range(r, c):
    return 0 <= r < N and 0 <= c < M

def is_orbit(r, c):
    return grid[r][c] == 0

def bfs():
    visit = [[[False] * 4 for _ in range(M)] for _ in range(N)]
    visit[start_r][start_c][start_d] = True
    bfs_queue = deque([(start_r, start_c, start_d, 0)])

    while bfs_queue:
        cur_r, cur_c, cur_d, count = bfs_queue.popleft()
        # 목표 위치와 방향에 도착하면 count 리턴
        if (cur_r, cur_c, cur_d) == (end_r, end_c, end_d):
            return count

        # 1, 2, 3칸 직진
        for step in range(1, 4):
            next_r = cur_r + dr[cur_d] * step
            next_c = cur_c + dc[cur_d] * step
            next_d = cur_d

            if in_range(next_r, next_c):
                if is_orbit(next_r, next_c) and not visit[next_r][next_c][next_d]:
                    bfs_queue.append((next_r, next_c, next_d, count + 1))
                    visit[next_r][next_c][next_d] = True

        # 방향 바꾸기 - 왼쪽 90도, 오른쪽 90도
        for next_d in rotate_all_dir[cur_d]:
            if not visit[cur_r][cur_c][next_d]:
                bfs_queue.append((cur_r, cur_c, next_d, count + 1))
                visit[cur_r][cur_c][next_d] = True

N, M = tuple(map(int, input().split()))
grid = [list(map(int, input().split())) for _ in range(N)]
start_r, start_c, start_d = tuple(map(int, input().split()))
end_r, end_c, end_d = tuple(map(int, input().split()))

start_r -= 1
start_c -= 1
start_d -= 1

end_r -= 1
end_c -= 1
end_d -= 1

print(bfs())

문제점

정점과 정점을 이어주는 간선이 모든 방향의 1, 2, 3 다음 칸에 있는 것이 아니다.

step에 있어 이전 step이 범위에 벗어나지 않고 궤도에 있어야만 다음 step이 갈 수 있다.

해결방안

현재방향과 현재 위치에서 1, 2, 3칸 직진할 때 반복문을 사용한다.

직진할 때, 범위에 벗어나거나 궤도가 아니면 다음 step으로 갈 수 없으므로 반복문을 종료한다.

 

5. 3차 풀이

from collections import deque

import sys
input = sys.stdin.readline

# 동 서 남 북
dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]

rotate_all_dir = ((2, 3), (2, 3), (0, 1), (0, 1))

def in_range(r, c):
    return 0 <= r < N and 0 <= c < M

def is_orbit(r, c):
    return grid[r][c] == 0

def bfs():
    visit = [[[False] * 4 for _ in range(M)] for _ in range(N)]
    visit[start_r][start_c][start_d] = True
    bfs_queue = deque([(start_r, start_c, start_d, 0)])

    while bfs_queue:
        cur_r, cur_c, cur_d, count = bfs_queue.popleft()
        # 목표 위치와 방향에 도착하면 count 리턴
        if (cur_r, cur_c, cur_d) == (end_r, end_c, end_d):
            return count

        # 1, 2, 3칸 직진
        for step in range(1, 4):
            next_r = cur_r + dr[cur_d] * step
            next_c = cur_c + dc[cur_d] * step
            next_d = cur_d

            if not in_range(next_r, next_c) or not is_orbit(next_r, next_c):
                break
            if not visit[next_r][next_c][next_d]:
                bfs_queue.append((next_r, next_c, next_d, count + 1))
                visit[next_r][next_c][next_d] = True

        # 방향 바꾸기 - 왼쪽 90도, 오른쪽 90도
        for next_d in rotate_all_dir[cur_d]:
            if not visit[cur_r][cur_c][next_d]:
                bfs_queue.append((cur_r, cur_c, next_d, count + 1))
                visit[cur_r][cur_c][next_d] = True

N, M = tuple(map(int, input().split()))
grid = [list(map(int, input().split())) for _ in range(N)]
start_r, start_c, start_d = tuple(map(int, input().split()))
end_r, end_c, end_d = tuple(map(int, input().split()))

start_r -= 1
start_c -= 1
start_d -= 1

end_r -= 1
end_c -= 1
end_d -= 1

print(bfs())

 

6. 풀이 후 알게된 개념과 소감

• 백트레킹하려고 하는데, N이 크기에 다른 방법으로 풀어야 하는 문제다.
• 위의 문제는 최소 명령의 개수를 구해야 하는데, 그러려면 그래프의 최단 거리를 구해줘야 한다.
• 일반적인 BFS 문제가 아닌, 방향 바꾸는 행위와 1,2,3칸 직진이 추가된 그래프를 정의하고 해당 그래프를 BFS 탐색하는 문제다.
• 위의 문제는 도착지점 뿐만아니라 도착지점의 방향도 고려해야 한다. 그러므로 visit를 grid의 크기대로 그리되, 각 위치별로 4방향(동서남북) 정보를 담을 수 있도록 * 4 해주었다.