프로그래머스 게임 맵 최단거리(Python) - DFS, BFS

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

프로그래머스

 

🎀해결 방법

문제 읽자마자 내가 좋아하는 DFS로 풀기 시작

정확성 테스트를 통과 못해서 visited를 1로 되돌려주는 코드를 추가하니 정확성 테스트를 통과했다

 

DFS에서 최선의 방법이라고 생각했지만 효율성 테스트는 통과하지 못했다

 

그래서 BFS로 수정하니 바로 통과했다

 

✨DFS - 효율성 테스트 실패

answer = 10**5

def solution(maps):
    global answer 
    h = len(maps)
    w = len(maps[0])
    visited = [[1]*w for _ in range(h)]
    def f(x,y):
        global answer 
        if x == h-1 and y == w-1:
            if answer > visited[x][y]:
                answer = visited[x][y]
        else:
            for d in [(-1,0),(0,-1),(0,1),(1,0)]:
                nx,ny = x+d[0], y+d[1]
                if 0 <= nx < h and 0 <= ny < w:
                    if maps[nx][ny] == 1 and visited[nx][ny] == 1:
                        visited[nx][ny] = visited[x][y] + 1
                        f(nx,ny)
                        visited[nx][ny] = 1
    f(0,0)
    if answer == 10**5:
        return -1
    else:
        return answer

✨BFS - 통과

answer = 10**5

def solution(maps):
    global answer 
    h = len(maps)
    w = len(maps[0])
    q = []
    visited = [[1]*w for _ in range(h)]
    def f(x,y):
        q.append((x,y))
        while q:
            (x, y) = q.pop(0)
            global answer 
            if x == h-1 and y == w-1:
                if answer > visited[x][y]:
                    answer = visited[x][y]
            else:
                for d in [(-1,0),(0,-1),(0,1),(1,0)]:
                    nx,ny = x+d[0], y+d[1]
                    if 0 <= nx < h and 0 <= ny < w:
                        if maps[nx][ny] == 1 and visited[nx][ny] == 1:
                            visited[nx][ny] = visited[x][y] + 1
                            q.append((nx,ny))
    f(0,0)
    if answer == 10**5:
        return -1
    else:
        return answer

#print(solution([[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]))