[백준]1726 로봇

1. 풀이

(1). bfs로 탐색을 할 때 핵심은 한칸씩 이동할 때 마다 해당 부분을 큐에 넣어주는것. 즉 해당 점까지의 최단거리를 탐색과 동시에 찾는것이다.

(2). 이 문제에서는 90도로 한번 방향을 전환하는 것 또한 한번의 이동으로 간주한다. 따라서 방향을 한번 이동한(왼쪽으로 90도, 오른쪽으로 90도) 후 큐에 넣어야 한다.

(3). 한번에 최대 3칸까지 이동할 수 있다. 그리고 이러한 이동도 한번의 횟수로 치기 때문에, 각각을 큐에 넣어주어야 한다.

(4). bfs 2차원 리스트에 차원을 하나 더 추가해서 (R,C)위치에서 turn 방향일때의 최솟값을 저장한다.

즉 (bfs[i][j][turn] : 시작점에서 에서 (i,j)점의 turn방향까지의 최솟값)

 

2. 소스코드

from collections import deque

dR=[0,1,0,-1]
dC=[1,0,-1,0]

if __name__=='__main__':
    M,N=map(int,input().split())
    L=[]
    for i in range(M):
        L.append(list(map(int,input().split())))
    stL=list(map(int,input().split()))
    for i in range(3):
        stL[i]-=1
    if stL[2]==1:
        stL[2]=2
    elif stL[2]==2:
        stL[2]=1

    endL=list(map(int,input().split()))
    for i in range(3):
        endL[i]-=1
    if endL[2]==1:
        endL[2]=2
    elif endL[2]==2:
        endL[2]=1

    bfs=[[[-1,-1,-1,-1] for j in range(N)] for i in range(M)]
    bfs[stL[0]][stL[1]][stL[2]]=0
    q=deque([[stL[0],stL[1],stL[2]]])
    ans=0
    while(q):
        '''
        for i in range(M):
            print(bfs[i])
        print()
        '''

        r,c,turn=q.popleft()
        if [r,c,turn]==endL:
            ans=bfs[r][c][turn]
            break
        #3번까지 직진한 후 q넣어
        for jump in range(1,4):
            tempR=r+dR[turn]*jump
            tempC=c+dC[turn]*jump
            if 0 <= tempR < M and 0 <= tempC < N and L[tempR][tempC] != 1 :
                if bfs[tempR][tempC][turn] == -1:
                    bfs[tempR][tempC][turn]=bfs[r][c][turn]+1
                    q.append([tempR,tempC,turn])
            else:
                break
        #3번 회전한 후 q넣어
        for k in [1,-1]:
            tempTurn=(turn+k)%4
            if bfs[r][c][tempTurn]==-1:
                bfs[r][c][tempTurn]=bfs[r][c][turn]+1
                q.append([r,c,tempTurn])

    print(ans)