[알고리즘] 게임 맵 최단거리 - bfs/dfs

 

✏️ 문제 링크:

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

프로그래머스

---

✏️ 소스코드v1  (정확도 100%,  효율성 0%) - dfs

from collections import deque
INF=10001

dx=[-1,0,1,0]
dy=[0,-1,0,1]
def solution(maps):
    n = len(maps)
    m = len(maps[0])
    def dfs(x,y,n,m,cnt):
        
        if x == n-1 and y == m-1:
            #print("도달", cnt)
            return cnt
        
        dx=[-1,0,1,0]
        dy=[0,-1,0,1]
        total_cnt = INF
        
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            
            if nx>=0 and nx<n and ny>=0 and ny<m:
                if maps[nx][ny]>=cnt or maps[nx][ny]==1:
                    maps[x][y]=cnt
                    #print("maps[",nx,"][",ny,"]로 이동")
                    
                    total_cnt = min(dfs(nx,ny,n,m,cnt+1), total_cnt)
                
        if total_cnt == INF:
            return INF
        
        return total_cnt
    
    
    
    result = dfs(0,0,n,m,1)
    
    if result == INF:
        return -1
    else: return result

이 문제를 처음 봤을 때 dfs가 먼저 떠올라 dfs로 코드를 썼었다.

정확도 테스트에서는 모두 '통과'가 나왔지만 효율성 테스트에서는 모두 '실패'가 나왔다.

그래서 보통 dfs보다는 bfs가 속도가 빠르기 때문에 bfs로 코드를 다시 짰다.

 

✏️ 소스코드v2  (정확도 100%,  효율성 0%) - bfs

from collections import deque

dx=[-1,0,1,0]
dy=[0,-1,0,1]
def solution(maps):
    n = len(maps)
    m = len(maps[0])
    
    queue = deque()
    queue.append((0,0))
    while queue: 
        x, y = queue.popleft()
        
        if x==n-1 and y==m-1:
            break
        now = maps[x][y]
        
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if nx>=0 and nx<n and ny>=0 and ny<m :
                next = maps[nx][ny]
                if next==1 or next > now:
                    maps[nx][ny] = now +1
                    queue.append((nx,ny))
                
    if maps[n-1][m-1] != 1:
        return maps[n-1][m-1]
    else:
        return -1

코드를 다시 짜봤지만 효율성 테스트는 그대로 였다.

 

아이디어:

- 현재의 블록에서 동서남북으로 탐색

- 다음블록이 1인 경우 queue에 담고, 그 블록의 값을 (현재의 블록+1) 해줌

- 또는 다음블록이 1이 아니고 더 큰 숫자일 경우에도 그 블록의 값을 (현재의 블록+1) 해줌.

   왜냐하면 다음블록이 더 크다는 것은 현재의 블록이 지나온 길이 더 빠르다는 것이므로

 

곰곰히 생각해보니 문제점을 찾았다.

동서남북으로 탐색할 때 다음블록이 1이 아닌 더 큰 숫자일 경우는 다음블록을 queue에 담지 않아도 된다.

왜냐하면 다음블록에 이미 값이 있다는 뜻은 빠르게 지나갈 수 있는 경로가 진작 지나갔다는 뜻!!

나중에 생각해보면 당연한 거지만.....문제 풀 때는 생각하지 못했다.

 

✏️ 소스코드v3  (정확도 100%,  효율성 100%) - bfs

from collections import deque

dx=[-1,0,1,0]
dy=[0,-1,0,1]
def solution(maps):
    n = len(maps)
    m = len(maps[0])
    
    queue = deque()
    queue.append((0,0))
    while queue: 
        x, y = queue.popleft()
        
        if x==n-1 and y==m-1:
            break
        now = maps[x][y]
        
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if nx>=0 and nx<n and ny>=0 and ny<m :
                next = maps[nx][ny]
                if next==1: #next>now를 제거
                    maps[nx][ny] = now +1
                    queue.append((nx,ny))
                
    if maps[n-1][m-1] != 1:
        return maps[n-1][m-1]
    else:
        return -1

성공! 

파란불💙