[파이썬/python] 백준 - 13901 로봇

문제

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

---

문제 설명

1. 특정 조건에 맞게 움직이는 로봇이 존재한다.
   1. 로봇은 사용자가 지정한 방향을 일직선으로 움직인다.
   2. 이동 중 벽이나 방문한 지역, 장애물을 만날 경우, 사용자가 지정한 다음 방향으로 움직인다.
   3. 사용자가 지정한 다음 방향이 없다면 맨 처음 방향으로 돌아가 과정을 반복한다.
   4. 움직일 수 없을 경우 동작을 멈춘다.
2. 이동이 끝났을 때 위치를 출력한다.

 

---

풀이

BFS를 통해 탐색하여 풀었다. 사실 단순 구현으로 풀어도 문제 없지만, 익숙한 알고리즘으로 풀이했다.

방향을 직접 해시를 통해 지정한다는 점이 문제의 특이점이라고 생각했다.

1. 해시를 통해 각 방향의 순서를 인덱스로 저장한다.
2. BFS를 진행하면서 도착점을 탐색한다.
   1. 이 때 방향이 최대 4방향이기 때문에 4로 나누어진 인덱스의 방향으로 탐색한다.
3. 결과 위치를 출력한다.

---

코드

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

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

R,C = map(int,input().split())
k = int(input())
board = [[0 for _ in range(C)] for _ in range(R)]

for i in range(k):
    r,c = map(int,input().split())
    board[r][c] = -1
sy,sx = map(int,input().split())

dir = list(map(int,input().split()))

for i in range(len(dir)):
    dir[i]-=1
queue = deque([(sy,sx,0)])
board[sy][sx] = 1

def bfs():
    while queue:
        y,x,di = queue.popleft()
        flag = 1
        for i in range(4):
            curr_d = dir[(di+i)%4]
            ny = y + dy[curr_d]
            nx = x + dx[curr_d]
            if ny < 0 or ny > R-1 or nx < 0 or nx > C-1 or board[ny][nx] in [1,-1]:
                continue
            queue.append((ny,nx,di+i))
            board[ny][nx] = 1
            flag = 0
            break
        if flag:
            print(y,x)
            return
bfs()

---

시간복잡도

• 단순 BFS로 탐색하기 때문에 배열의 크기인 R*C만큼의 시간이 소요되므로, 시간복잡도는 약 $O(10^6)$이다.