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

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

프로그래머스

 

문제 개요

게임 맵 최단거리

*각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리
*캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동
*게임 맵을 벗어난 길& 검은 부분은 갈 수 없습니다
*상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다

input
maps: 게임 맵의 상태
*n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열
*n, m 모두 1이상 100이하 자연수
*n, m모두 1인 경우는 없음.
*0은 벽이 있는 자리, 1은 벽이 없는 자리

내 캐릭터 위치 초깃값: (1,1) == 게임맵 좌측 상단
상대 캐릭터 초깃값: (n,m) == 게임맵 우측 하단

output
상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값
상대 팀 진영에 도착할 수 없을 때는 -1

 

 

1) BFS로 구현 + 효율성 최하

from collections import deque

def solution(maps):
    n = len(maps[0]) #가로
    m = len(maps) #세로
    answer = []
    queue = deque()
    queue.append(((1,1), [(1,1)]))
    
    while queue:
        (a,b), route = queue.popleft()
        neighbor = [(a+1,b), (a, b+1), (a-1, b), (a, b-1)]
        for (x,y) in neighbor:
            if (1<=x<=n) and (1<=y<=m) and ((x,y) not in route) and (maps[y-1][x-1] == 1):
                temp = route + [(x,y)]
                if (x==n) and (y==m):
                    answer.append(len(temp))
                else:
                    queue.append(((x,y), temp))        
    if not answer:
        return -1
    else:
        return min(answer)

 

• 가능한 neighbor을 추려내어 queue에 저장
• 각 노드마다 자신에게 도달하기까지 거쳐야 하는 visited를 temp를 활용하여 모두 저장
• 노드가 도착지점이 되었을 때 answer에 visited의 length를 저장 후 그 가운데 min을 구함
  → 아예 불필요한 절차. (무조건 첫번째 값이 answer가 되기 때문에 바로 return하면 됨)

2) BFS로 구현 + 효율성 하

from collections import deque

def solution(maps):
    n = len(maps[0]) #가로
    m = len(maps) #세로
    answer = 0
    queue = deque()
    queue.append(((1,1), [(1,1)]))
    
    while queue:
        (a,b), route = queue.popleft()
        neighbor = [(a+1,b), (a, b+1), (a-1, b), (a, b-1)]
        for (x,y) in neighbor:
            if (1<=x<=n) and (1<=y<=m) and ((x,y) not in route) and (maps[y-1][x-1] == 1):
                if (x==n) and (y==m):
                    answer = len(route)+1
                    return answer
                else:
                    temp = route + [(x,y)]
                    queue.append(((x,y), temp))
                    
                             
    if not answer:
        return -1

• min 절차 제외하고 answer 나오자마자 바로 return.
• 그렇다고 answer를 visited의 length로 구할 수 없음.
  answer에서 원하는 '방문 노드'와 BFS에서의 'visited'의 기능이 다르기 때문.
  → 각 경로의 vistied가 아니라, 큐 생성 시 제외할 노드를 가리기 위함.
• 여전히 효율성 0점인 이유는?
  1. 각 노드마다 visited를 별도로 구해서 저장하는 게 최악의 비효율.
  2. '노드가 도착지점이 되자마자' 그것이 거쳐 온 노드 개수가 바로 answer가 됨. 이 지점을 활용해야 하는데!
  3. 경로마다 거쳐 온 노드 개수가 다른데 이건 BFS의 Depth를 활용하면 된다!

→ visited 기능을 구현하면서 + BFS의 Depth를 구하는 방법은?

 

3) BFS로 구현 + Depth 활용 + 효율성 최상 ⭐⭐⭐

from collections import deque

def solution(maps):
    n = len(maps[0]) #가로
    m = len(maps) #세로
    answer = 0
    queue = deque()
    queue.append((1,1))
    
    while queue:
        a,b = queue.popleft()
        neighbor = [(a+1,b), (a, b+1), (a-1, b), (a, b-1)]
        for (x,y) in neighbor:
            if (1<=x<=n) and (1<=y<=m) and (maps[y-1][x-1] == 1):
                    queue.append((x,y))
                    maps[y-1][x-1] = maps[b-1][a-1] + 1
                                 
    if maps[m-1][n-1] == 1:
        return -1
    else:
        return maps[m-1][n-1]

• 명시적인 visited 리스트는 없지만 그 기능을 하는 것이 if maps[y-1][x-1] == 1 조건
  원래 0이면(막혀 있으면) 로직 상 0 초과의 값을 가질 수 없음
  1이면 '뚫려 있지만' '아직 방문된 적 없다'를 의미함
  1 초과 값이면 '방문된 적 있다' & 해당 값은 '나를 방문하기까지 거쳐야 하는 노드 개수'를 의미함.
• BFS의 depth는 maps[y-1][x-1] = maps[b-1][a-1] + 1
  '직전 위치의 값에 +1' 한 값으로 갱신

 

---

이와 별개로, BFS 구현 시 주의해야 하는 점. (특히 효율성)

- 혹시 본인의 코드가 방문체크를 큐에서 꺼낼 때 하고있는건 아닌지 확인해보세요.
방문체크를 큐에 넣을 때 해야 효율성이 통과됩니다. 그 이유는 만약 꺼낼 때 방문체크를 하게되면, 하나의 블럭을 꺼내서 통로를 탐색할 때, 이미 큐에 들어있는 블럭을 또 큐에 넣을 수도 있기 때문입니다.

- https://school.programmers.co.kr/questions/23794

프로그래머스