[BOJ / 백준] 1726 로봇 (G3 / BFS) - Python

링크

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

 

 

 

 

문제 해석

로봇은 방향과 위치를 가지고 있고, 매 턴 [ 좌로 회전, 우로 회전, 한 칸 앞으로 이동, 두 칸 앞으로 이동, 세 칸 앞으로 이동 ]이 가능하다.

 

이 때 원하는 도착지점에 원하는 회전상태로 이동하는 최단 시간을 구하라.

 

 

입력

첫 번째 줄 : m, n <= 100
  m : 직사각형의 세로 길이
  n : 직사각형의 가로 길이

m개의 줄 : 지도 정보
  0 : 갈 수 있는 길
  1 : 갈 수 없는 길
다음 줄 : sx, sy, sd 
  로봇의 출발 지점 위치, 바라보는 방향
  동쪽은 1, 서쪽은 2, 남쪽은 3, 북쪽은 4
마지막 줄 : ex, ey, ed
  도착점의 위치, 바라봐야할 방향


출력
원하는 방향으로 이동시키는데 필요한 최소 명령 횟수

 

 

 

 

풀이 & 코드 해석

결국 도착 지점까지 도달하는데 걸리는 시간을 구하는 문제로 BFS를 사용하면 풀 수 있을 것이라 생각하였습니다.

 

단 회전을 하는데도 시간이 소요되므로, 회전 역시 방문처리를 진행하는 것이 옳다고 생각하였습니다.

 

BFS의 시간 복잡도는 O(n * m)이고, 여기에 4번의 회전을 추가하더라도 충분히 시간 내에 풀 수 있을 것이라 판단하였습니다.

 

 

BFS를 진행하기 전 로봇의 회전 각과, 도착지의 회전 각이 좌우 회전 정보를 저장하는데 불편하다고 생각하였습니다.

(회전은 상우하좌와 같이 순서대로 진행하면 편한데 입력 값은 상화좌우 순으로 작성되어 있습니다)

 

문제를 푸는데 입력 값을 변경하는 것은 영향이 없다고 판단하였고, 입력 값을 사용하기 용이한 방식으로 변경한 후 BFS를 진행하였습니다.

 

 

BFS에서는 왼쪽으로 회전한 위치, 오른쪽으로 회전한 위치, 한 칸 ~ 세 칸 전진한 위치를 각각 Queue에 삽입하였습니다.

 

 

 

 

코드

from collections import deque

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]


def bfs():
    global m, n, sx, sy, sd, ex, ey, ed

    q = deque()
    q.append([sd, sx, sy])
    v[sd][sx][sy] = 0

    while q:
        pd, px, py = q.popleft()
        now = v[pd][px][py]

        if px == ex and py == ey and pd == ed:
            return now

        # 좌로 회전
        nd = (pd + 3) % 4
        if v[nd][px][py] == -1:
            v[nd][px][py] = now + 1
            q.append([nd, px, py])

        # 우로 회전
        nd = (pd + 1) % 4
        if v[nd][px][py] == -1:
            v[nd][px][py] = now + 1
            q.append([nd, px, py])

        # 앞으로 한칸 이동, 앞으로 두칸 이동, 앞으로 세칸 이동
        for d in range(1, 4):
            nx = px + dx[pd] * d
            ny = py + dy[pd] * d

            if nx < 0 or nx >= m or ny < 0 or ny >= n:
                continue

            # 갈 수 없는 길
            if arr[nx][ny] == 1:
                break

            # 이미 지나간 길
            if v[pd][nx][ny] != -1:
                continue

            v[pd][nx][ny] = now + 1
            q.append([pd, nx, ny])


m, n = list(map(int, input().split()))

v = [[[-1] * n for _ in range(m)] for _ in range(4)]

arr = []

for i in range(m):
    arr.append(list(map(int, input().split())))

sx, sy, sd = list(map(int, input().split()))
ex, ey, ed = list(map(int, input().split()))

sx -= 1; sy -= 1
ex -= 1; ey -= 1
sd = (sd + 3) % 4
ed = (ed + 3) % 4

if sd == 0:
    sd = 1
elif sd == 1:
    sd = 3
elif sd == 2:
    sd = 2
else:
    sd = 0

if ed == 0:
    ed = 1
elif ed == 1:
    ed = 3
elif ed == 2:
    ed = 2
else:
    ed = 0

print(bfs())

# for i in range(4):
#     for j in range(m):
#         print(v[i][j])
#     print()

 

 

 

 

발생한 문제 & 해결 방안

초반에 한 칸, 두 칸, 세 칸 앞으로 전진할 때 1을 만나면 continue를 하는 방식으로 구현하였다.

 

그랬더니 0 1 0 0 (내 위치는 0, 0)과 같은 상황에서 한 칸은 건너갈 수 없지만 두 칸, 세 칸은 건너가는 문제가 발생하였다.

 

코드 결과 값을 보고 바로 해결하였지만, 처음부터 조건의 의식하고 푸는 습관을 가지는 것이 중요하겠다.

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java