(Python/파이썬) - 백준(BOJ) 1726번 : 로봇

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

1726번: 로봇

---

• 문제 : 

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

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

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

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

 

 

 

---

• 풀이 :

그래프 탐색 문제였습니다.

 

처음에 DFS로 풀려고 시도하였으나 시간초과를 해결하지 못하여 BFS로 다시 풀었습니다.

 

풀이입니다.

 

1. bfs로 board를 상,우,하,좌의 순서로 탐색합니다. 문제에서 주어진 방향은 1 - 동, 2 - 서, 3 - 남, 4 - 북 이기 때문에 각각 0,1,2,3의 인덱스로 변환하기 위한 배열을 추가해주었습니다.

 

2. visited 배열은 3차원 배열로 z축은 동,서,남,북의 4 방향으로 각 방향에서 해당 칸으로 이동한 경우가 있는지 없는지 여부를 체크합니다.

 

3. 한 방향에 대해 해당 방향으로 K 칸( 1 <= K <= 3 )을 이동하는 경우를 확인하고 해당 방향으로 이동할 수 있는 경우.

(방문하지 않았고 주어진 board를 벗어나지 않으며 해당 방향으로 레일이 깔려있다.) queue에 넣어줍니다.

 

4. 현재 탐색중인 칸에서 들어온 방향을 제외한 나머지 3 방향에 대해서 로봇을 회전시킨 후 queue에 넣어줍니다.

(회전시킬 때 회전 각도 (0 ~ 180)에 대해 회전 횟수를 카운트해주어야 합니다.)

 

5. 목적지에 맞는 방향으로 도착할 경우 그 때의 cnt값을 반환합니다.

 

 

 

 

---

• 소스코드 : 

 

DFS - 시간초과로 인한 실패

import sys
input = sys.stdin.readline

dx = [-1,0,1,0]
dy = [0,1,0,-1]
d = [0,1,2,1]
dd = [0,1,3,2,0]
answer = float("inf")
def dfs(x,y,dir, cnt):
    global answer
    if x == tx-1 and y == ty-1 :
        answer = min(answer, cnt+d[abs(dir-dd[td])])
        return
    if cnt < answer:
        for i in range(4):
            rot = abs(dir - i) % 4
            ax,ay = x,y
            for _ in range(3):
                ax += dx[i]
                ay += dy[i]
                if 0 <= ax < N and 0 <= ay < M and board[ax][ay] == 0:
                    board[ax][ay] = 1
                    dfs(ax,ay,i,cnt + 1 + d[rot])
                    board[ax][ay] = 0
                else:
                    break


N,M = map(int,input().split())
board = [list(map(int,input().split())) for _ in range(N)]
fx,fy,fd = map(int,input().split())
tx,ty,td = map(int,input().split())
board[fx-1][fy-1] = 1
dfs(fx-1,fy-1,dd[fd],0)
print(answer)

 

BFS- 성공

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


def bfs():
    queue = deque()
    queue.append([fx-1,fy-1,dd[fd],0])
    visited = [[[-1 for _ in range(4)] for _ in range(M)] for _ in range(N)]
    visited[fx-1][fy-1][dd[fd]] = 0
    while queue:
        x,y,dir,cnt = queue.popleft()
        if x == tx-1 and y == ty-1 and dir == dd[td]:
            return cnt
        ax,ay = x,y
        for _ in range(3):
            ax += dx[dir]
            ay += dy[dir]
            if 0 <= ax < N and 0 <= ay < M and board[ax][ay] == 0:
                    if visited[ax][ay][dir] == -1:
                        visited[ax][ay][dir] = 0
                        queue.append([ax,ay,dir,cnt+1])
            else:
                break
        for i in range(4):
            if visited[x][y][i] == -1 and dir != i:
                visited[x][y][i] = 0
                queue.append([x,y,i,cnt+d[abs(i-dir)]])

N,M = map(int,input().split())
board = [list(map(int,input().split())) for _ in range(N)]
fx,fy,fd = map(int,input().split())
tx,ty,td = map(int,input().split())
print(bfs())