[Softeer 인증평가 1차 기출] 로봇이 지나간 경로(파이썬)

https://softeer.ai/practice/info.do?idx=1&eid=577&sw_prbl_sbms_sn=118275 

Softeer

 

이 문제는 bfs유형중에서 상당히 독특했던 문제.

처음에 문제를 파악하기 어려워서

체감적으로 어렵게 느껴졌다가

문제를 이해하니 할만했습니다.

 

1. 시작점이 어디인가?

-->시작점을 구하는 걸 생각하니 머리가 아팠습니다.

#이 칠해진 모든 지도를 다 돌아가면서

#이 있는 지점을 시작점으로 하나씩 두고 시작한다면

시간초과가 뜰 것이 뻔하기 때문입니다.

문제에서

'로봇이 앞으로 두칸 움직인다'라는 조건이 붙었기 때문에

시작/끝점을 구하는 게 쉬워졌습니다.

만약에 로봇이 한칸씩 움직인다면

No에서 그린 경우가 가능하겠지만

2칸씩 움직이는 조건이 있어서 불가능합니다.

그래서 이 문제는 시작,끝점을 구하는 게 친전한 문제.

 

2. 명령을 어떻게 구할 것인가

-->시작경로에서 bfs를 해주면서

지나간 경로를 리스트에 넣었습니다.

그 후, 모든 #을 지나갔으면(count가 #의 갯수가 같다면)

해당 경로를 받아줍니다.

그 다음 명령을 다음과 같이 구했습니다.

 

cnt-->얼마나 움직였는지에 대한 변수

 A-->이전좌표+현재방향대로 움직일 때 지금좌표가 나온다면 cnt+1

cnt==2라면,cnt=0을 해주면서 A를 추가

L-->이전좌표+(왼쪽으로 틀어서 움직일때)지금좌표가 나온다면 cnt+1을 해주면서

L을 추가

R-->이전좌표+(오른쪽으로 틀어서 움직일때)지금좌표가 나온다면 cnt+1을 해주면서

R을 추가

 

import sys
from collections import deque

H,W=map(int,input().split())

maps = []
direct = {0:'>', 1:'^',2:'<', 3:'v'}
ans = [[0, 0, 0, 'a'*1000], '']
total = 0
for i in range(H):
    temp = input()
    total += temp.count('#')
    maps.append(temp)


dx=[0,-1,0,1]
dy=[1,0,-1,0]
sp=[]
#시작점 끝점 파악하기
for x in range(H):
    if sp:
        break
    for y in range(W):
        if sp:
            break
        if maps[x][y]=='#':
            count=0
            di=0
            flag=True
            for d in range(4):
                nx=x+dx[d]
                ny=y+dy[d]

                if nx<0 or nx>=H or ny<0 or ny>=W:
                    continue

                if maps[nx][ny]=='#':
                    count+=1
                    di=d

                if count>1:
                    flag=False
                    break

            if flag:
                sp.append((x,y,di))

start=sp[0]
sx,sy,di=start
print(sx+1,sy+1)
q=deque()
path=[]
path.append((sx,sy))
q.append((sx,sy,path,1))
ans=set()
#bfs를 해준다
while q:
    x,y,pa,cnt=q.popleft()
    if cnt==total:
        ans=pa
        break
    for d in range(4):
        nx=x+dx[d]
        ny=y+dy[d]

        if nx<0 or nx>=H or ny<0 or ny>=W:
            continue

        if (nx,ny) in pa:
            continue
        if maps[nx][ny]=='.':
            continue
        pa.append((nx,ny))
        q.append((nx,ny,pa,cnt+1))


gd=di
answer=""
cnt=0
print(direct[di])
for i in range(1,len(ans)):
    nx,ny=ans[i][0],ans[i][1]
    bx,by=ans[i-1][0],ans[i-1][1]

    #앞으로 전진
    if bx+dx[gd]==nx and by+dy[gd]==ny:
        cnt+=1
        gd=gd
        if cnt==2:
            cnt=0
            answer+='A'
    #왼쪽으로 틀 경우


    elif bx+dx[(gd+1)%4]==nx and by+dy[(gd+1)%4]==ny:
        answer+='L'
        gd=(gd+1)%4
        cnt+=1

    #오른쪽으로 틀 경우

    elif bx+dx[(gd-1)%4]==nx and by+dy[(gd-1)%4]==ny:
        answer+='R'
        gd=(gd-1)%4
        cnt+=1

    #print(answer,gd)
print(answer)