[백준 1726번] 로봇(파이썬)

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

1726번: 로봇

나온지 좀 된 문제인만큼

푸는 사람도 많은 문제.

그리고 고통받는 사람도 참 많은 문제.

 

이 문제는 단순한 bfs로 풀면 안 됩니다.

'방향'이 중요하기 때문.

방향에 따라서 움직임이 카운트가 되기 때문에

이를 신경써줘야합니다.

주의할 부분들 살펴보면

 

1. K이동-->최대 3개까지 이동이 가능합니다.

K이동시 벽을 만나면 멈춥니다.

단, 이전에 방문한 곳을 또 지나칠 수는 있습니다.

만약 0 0 0 인데, 앞에 두개 0은 방문한 이력이 있어도

마지막 0까지 갈 수 있습니다.

 

2. 방향-->저는 visited를 3차원으로 선언해주어서

방향마다 탐색하는 쪽으로 코드를 구성했습니다.

그리고 방향구현할 때

자동적으로 (dir+1)%4 

이렇게 구현하실 분들이 많을 겁니다.

이 문제는 자세히 읽어보면

동 서 남 북이

0 1 2 3 으로 되어있어서

그렇게 구현하면 안되고

직접 빡구현을 좀 해줘야합니다.

 

3. 정답을 입력할 때

무조건 목표지점,방향에 왔다고

바로 cnt값을 출력하면 틀릴 수 있습니다.

혹시나 그 값보다 더 작은 값이 나올 수 있기 때문에

모든 값을 다 받은 뒤에

출력해야합니다.

 

#백준 1726번 로봇
from heapq import heappop,heappush
dx=[0,0,1,-1]
dy=[1,-1,0,0]
N,M=map(int,input().split())


room=[list(map(int,input().split())) for _ in range(N)]
rx,ry,rd=map(int,input().split())
rx-=1
ry-=1
rd-=1
ex,ey,ed=map(int,input().split())
ex-=1
ey-=1
ed-=1
visited=[[[False]*4 for _ in range(M)] for _ in range(N)]
visited[rx][ry][rd]=True
q=[]
ans=1e9
heappush(q,[0,rx,ry,rd])

#78% 오답 해결
# 탐색하다가 정답지점,정답방향에 오면 visited로 넣지 않고 바로 답과 최대최소 비교해준다
#방문처리하면 다시 또 들어가지 못하게 되면서 더 작은 값이 나올 경우 최신화가 안되는 모양.
while q:
    cnt,x,y,d=heappop(q)

    if x==ex and y==ey and d==ed:
        ans=min(ans,cnt)
        continue
    #현재 보는 방향에서 직진
    nx=x
    ny=y
    count=1
    while 0<=nx+dx[d]<N and 0<=ny+dy[d]<M and count<=3 and room[nx+dx[d]][ny+dy[d]]==0:
        nx+=dx[d]
        ny+=dy[d]
        if nx==ex and ny==ey and d==ed:
            ans=min(ans,cnt+1)

        elif visited[nx][ny][d]==False:
            visited[nx][ny][d]=True

            heappush(q,[cnt+1,nx,ny,d])
        count+=1

    #방향을 틀어줌-->좌 우 180
    #180도
    if d==0:
        nd=1
    elif d==1:
        nd=0
    elif d==2:
        nd=3
    elif d==3:
        nd=2

    if not visited[x][y][nd]:
        if x==ex and y==ey and nd==ed:
            ans=min(ans,cnt+2)
        else:
            visited[x][y][nd]=True
            heappush(q,[cnt+2,x,y,nd])
    #90도
    if d==0 or d==1:
        change=[2,3]
    else:
        change=[1,0]
    for c in change:
        if not visited[x][y][c]:
            if x==ex and y==ey and c==ed:
                ans=min(ans,cnt+1)
            else:
                visited[x][y][c] = True
                heappush(q, [cnt + 1, x, y, c])
print(ans)

 

맞왜틀을 참 많이했던 문제.

게시판에 있는 예제케이스들을 꼼꼼히 보면서

코드를 계속 수정하면서

많이 배워나갔던 좋은 문제입니다.