게임 맵 최단거리

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

프로그래머스

 

어디선가 토마토를 풀면서 생각해낸 방법 이런 2차원의 길 찾기나 미로 같은 문제에는 적용 가능하다 그리고 이게 bfs/dfs라는 걸 알았다

일단 지금 위치에서 가능한 곳을 탐색한다 사방으로 다음 좌표값이 0보다 크고 행의 개수나 열의 개수보다 작아야 하고 여기에서 특징은 0이면 못 가는 곳이다 조건을 만족한다면 만족하는 좌표로 가고 좌표의 값을 0으로 바꿔 못 가게 한다 이렇게 하지 않는다면 같은 곳만 왔다 갔다 무한 루프가 걸리게 된다 한번 진행하였을 때 갈 수 있는 곳을 리스트에 담고 목적지가 나올 때까지 계속 반복한다 만약 가능 중에 목적지가 나오면 바로 리턴하고 끝났는데도 목적지를 못 만나면 -1을 리턴한다

 

def solution(t):
    r=len(t)
    l=len(t[0])
    tt=[[0,0]]
    s=1
    while tt:
        n=[]
        s+=1
        for x,y in tt:
            for a,b in [[-1,0],[1,0],[0,-1],[0,1]]:
                if 0<=x+a<r and 0<=y+b<l and t[x+a][y+b]==1:
                    if (x+a,y+b)==(r-1,l-1):
                        return s
                    t[x+a][y+b]=0
                    n.append([x+a,y+b])
        tt=n
    return -1