p_등굣길_42898

문제

최단거리개수의합
아래와 오른쪽으로만갈수있음

답

bfs를 이용해야겠다라는 생각을했다. 그리고 이미 방문한곳을 아예갈수 없는게 아니라 같은 스텝의 경우는 허용되기에 이부분을 어떻게 처리할지 고민이 깊었다.
근데 고민할 필요가없엇다 아래와 오른쪽으로만 갈 수 있다는 조건 이있었기에 각기 다른방향에서오는 최단거리를 고대로 합해주는 식으로 하면됐었다.
이때 주요포인트가 각자 다른 거리지만 한목적지를 향해서 오는 것에 대해서는 나중에 방문햇던 리스트목록에 set으로 넣어야한다는 것이다. 아니면 중복처리가 된다.

def solution(m, n, puddles):
    ways =[[0,1],[1,0]]
    visit =[[0]*m for _ in range(n)]
    q = {(0,0)}
    visit[0][0] = 1    
    
    while q and visit[n-1][m-1] == 0:
        tq = set([])
        for y,x in q:
            before = visit[y][x]
            for dy,dx in ways:
                ny = y+dy
                nx = x+dx
                if [nx+1,ny+1] in puddles:
                    continue
                if 0<=ny and 0<=nx and ny<n and nx<m:
                    visit[ny][nx] +=before
                    tq.add((ny,nx))
        q = tq
    return visit[n-1][m-1] % 1000000007