[BFS] 프로그래머스 - 게임 맵 최단거리

✨해결포인트

1. '최단거리'를 구해야 하는 것이기 때문에 DFS보다 BFS가 유리한 문제였다.

 

2. 처음 시도에서 DFS(재귀함수)를 활용해

- 방문가능한 노드인 경우 방문한 노드를 0으로 바꿔주고

- 동서남북 방향으로 순차적으로/재귀적으로 길을 탐색하며 count를 늘려주며

- 더이상 방문할 수 없을 때 return 하도록 코드를 짰다.

 

결과, 테스트케이스는 통과하나 효율성테스트를 통과하지 못했다.

 

3. 논리는 같으나, queue를 활용하는 것으로(재귀함수x) 코드를 수정했다.

- 시작지점을 enqueue해주고

- queue 가장 앞의 지점을 방문하며 dequeue

- 방문지점을 기준으로 거리가 1인(동/서/남/북) 지점들 중 방문할 수 있는 지점들을 enqueue

- queue가 빌때까지 반복

 

결과, 효율성테스트를 통과했다.

+) 동/서/남/북 방향으로 지점을 방문하는 반복적인 코드를 간결하게 줄이면 더 좋을 듯 하다.

 

✨시도1 코드 (DFS)

import copy
def solution(maps):
    n = len(maps)
    m = len(maps[0])
    now = [0,0]
    global lst
    lst = []
    initial_map = [maps][0]
    def visit(start, tmp_map, count):
        start = copy.deepcopy(start)
#         print(start)
        if tmp_map[start[0]][start[1]]==0:
#             print("못가는길")
            return
        else: #방문가능한 노드에 대해
            now_map = copy.deepcopy(tmp_map)
            now_map[start[0]][start[1]] = 0
#             for i in now_map:
#                 print(i)
            if start==[n-1,m-1]:
                lst.append(count+1)
#                 print("끝######################")
                return
            else:
                dong = [start[0],start[1]+1]
                seo = [start[0],start[1]-1]
                nam = [start[0]+1,start[1]]
                book = [start[0]-1,start[1]]
                if dong[1]<m:
#                     print("동", count+1)
                    visit(dong,now_map,count+1)
                if nam[0]<n:
#                     print("남", count+1)
                    visit(nam,now_map,count+1)
#                     print(start) #[1,4]
                if book[0]>=0:
#                     print("북", count+1)
                    visit(book,now_map,count+1)
                if seo[1]>=0:
#                     print("서", count+1)
                    visit(seo,now_map,count+1)
    answer = visit(now, initial_map, 0)
    if len(lst)==0:
        return -1
    else:
        return min(lst)

 

 

 

✨최종 코드 (BFS)

def solution(maps):
#     count  = 0
    queue = []
    start = [0,0,1]
    n = len(maps)
    m = len(maps[0])
    
    # 첫 노드 추가
    maps[start[0]][start[1]]=0
    queue.append(start)
    
    # 다음노드
    while len(queue)!=0:
        now = queue.pop(0)
#         maps[now[0]][now[1]]=0
#         count+=1
        if now[0]== n-1 and now[1]==m-1:
            break
        dong = [now[0],now[1]+1,now[2]+1]
        seo = [now[0],now[1]-1,now[2]+1]
        nam = [now[0]+1,now[1],now[2]+1]
        book = [now[0]-1,now[1],now[2]+1]
        
        if dong[1]<m and maps[dong[0]][dong[1]]==1:
            queue.append(dong)
            maps[dong[0]][dong[1]]=0
        if seo[1]>=0 and maps[seo[0]][seo[1]]==1:
            queue.append(seo)
            maps[seo[0]][seo[1]]=0
        if nam[0]<n and maps[nam[0]][nam[1]]==1:
            queue.append(nam)
            maps[nam[0]][nam[1]]=0
        if book[0]>=0 and maps[book[0]][book[1]]==1:
            queue.append(book)
            maps[book[0]][book[1]]=0
    if now[0]== n-1 and now[1]==m-1:
        return now[2]
    else:
        return -1