[python] 백준 1726 로봇

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

1726번: 로봇

 

 

문제 해결

• BFS를 이용해서 새로운 길을 가면서 최소 거리를 찾는 것은 쉽게 알 수 있다.
• 그러나 방향을 좌, 우로 90도만큼 트는 것을 생각해야하고 직선으로 1칸부터 3칸까지 갈 수 있다는 것을 생각해야한다.
  • visited에 바라보는 방향까지 포함시켜서 3차원 리스트로 저장을 하도록 한다.
• 회전은 90도만 가능하므로 동,서일 때는 남,북으로 회전 가능하고 남,북일 대는 동,서 방향으로 회전 가능하다.
• 중간에 3칸을 가고 싶어도 벽(1)이 있으면 갈 수 없으므로 1칸부터 3칸까지 반복문을 이용해서 갈 수 있으면 que에 넣고 아니면 break를 이용해서 더 못간다는 알고리즘을 작성한다.
• 조건을 분리해서 코드를 짜면 충분히 짤 수 있는 난이도

 

CODE

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

def bfs():
    dx = (0,0,0,1,-1)
    dy = (0,1,-1,0,0)

    visited = [[[0]*5 for _ in range(n)] for _ in range(m)]
    visited[sx-1][sy-1][sdir] = 1
    que = deque()
    que.append((sx-1,sy-1,sdir,0))

    while que:
        x, y, dir, cnt = que.popleft()
        if (x,y,dir) == (ex-1, ey-1, edir):return cnt
        for dis in range(1,4):
            nx = x + dx[dir]*dis
            ny = y + dy[dir]*dis
            nd = dir
            if not (0<=nx<m and 0<=ny<n) or board[nx][ny]:break
            if visited[nx][ny][nd]:continue
            que.append((nx,ny,nd,cnt+1))
            visited[nx][ny][nd] = 1
        
        if dir==1 or dir==2:
            if not visited[x][y][3]:
                visited[x][y][3] = 1
                que.append((x,y,3,cnt+1))
            if not visited[x][y][4]:
                visited[x][y][4] = 1
                que.append((x,y,4,cnt+1))
        else:
            if not visited[x][y][1]:
                visited[x][y][1] = 1
                que.append((x,y,1,cnt+1))
            if not visited[x][y][2]:
                visited[x][y][2] = 1
                que.append((x,y,2,cnt+1))

if __name__=='__main__':
    m, n = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(m)]
    sx, sy, sdir = map(int, input().split())
    ex, ey, edir = map(int, input().split())
    result = bfs()
    print(result)