리코쳇 로봇

https://school.programmers.co.kr/learn/courses/30/lessons/169199

프로그래머스

 

 

생각보다 어렵다
일단 이것도 2차원 형태로 길을 찾는 문제다 그러면 bfs 사용
아마도 dfs 보다 bfs 가 빠를 듯 n 번째에 출구를 찾으면 바로 끝나기 때문에?
어쨌든 bfs를 사용하는데 약간 방식이 애매하다 한 칸이 아니라 끝까지 미끄러지기 때문에
처음 시작점에서 시작해서 사방으로 가는데 1칸이 아니라 벽을 만나거나 모서리까지 갈 때까지 while 문으로 반복한다
만약 while 문을 탈출한다는 건 벽이기 때문에 그 점이 도착점이다
한번 방문한 곳을 재방문 하면 무한 루프가 생기기 때문에 딕셔너리를 사용해 지나온 곳은 체크한다
이런 식으로 시작점에서 사방 끝으로 그리고 도착한 곳 모두에서 다시 각각 사방 끝으로 가는 걸 반볻하다가 탈출구를 만나면 지금까지
반복한 횟수를 리턴
끝날 때까지 리턴하지 않는다면 길이 없다는 뜻이므로 -1 리턴

 

def solution(t):
    r=len(t)
    l=len(t[0])
    a=0
    t1=[]
    for i in range(r):
        for j in range(l):
            if t[i][j]=="R":
                t1.append([i,j])
            if t[i][j]=="G":
                tx,ty=i,j
    t2=[] 
    d={}
    n=1
    while t1:
        t2=[]
        for i,j in t1:
            for x,y in [[1,0],[-1,0],[0,1],[0,-1]]:
                x1=x
                y1=y
                while 0<=i+x1<r and  0<=j+y1<l and t[i+x1][j+y1]!="D":
                    x1+=x
                    y1+=y
                if (i+x1-x,j+y1-y)==(tx,ty):
                    return n
                d.setdefault((i+x1-x,j+y1-y),1)
                if d[(i+x1-x,j+y1-y)]:
                    d[(i+x1-x,j+y1-y)]=0
                    t2.append((i+x1-x,j+y1-y))
                #print(i+x1-x,j+y1-y)
        n+=1
        t1=t2
    return -1