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

문제 설명

ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.

지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.

위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.
아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.

• 첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.

• 두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.

위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.

만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.

게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

---

제한사항

• maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
  • n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
• maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
• 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

---

입출력 예

maps	answer
[[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]]	11
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]]	-1

입출력 예 설명

입출력 예 #1
주어진 데이터는 다음과 같습니다.

캐릭터가 적 팀의 진영까지 이동하는 가장 빠른 길은 다음 그림과 같습니다.

따라서 총 11칸을 캐릭터가 지나갔으므로 11을 return 하면 됩니다.

입출력 예 #2
문제의 예시와 같으며, 상대 팀 진영에 도달할 방법이 없습니다. 따라서 -1을 return 합니다.

---

1. DFS - Backtracking

from copy import deepcopy

def go_to_dest(now_coord, maps, destination, path, minpath):
    if path > minpath  and path > 1 and minpath > 0: #이미 minpath를 넘은 경우 리턴
        return minpath
    
    if now_coord == destination: #도착점에 도착하면 minpath 리턴
        minpath = min(path, minpath) if path > 1 and minpath > 0 else path
        maps[now_coord[0]][now_coord[1]] = minpath
        return minpath
    else: 
        maps_ = deepcopy(maps)
        now_x, now_y = now_coord[0], now_coord[1]
        xs = [-1, 1, 0, 0]
        ys = [0, 0, -1, 1]

        for x,y in zip(xs, ys):
            next_x, next_y = now_x+x, now_y+y
            if maps_[next_x][next_y] == 1:
                maps_[next_x][next_y] = path
                #도착점까지 방문할 수 있는 경로 모두 탐방하고, minpath를 도출
                minpath = go_to_dest((next_x, next_y), maps_, destination, path+1, minpath) 
    return minpath

def solution(maps):  
    # out of range 방지 위해서, map의 가장자리에 1을 붙임
    destination = (len(maps), len(maps[0]))
    newmap = [[0 for _ in range(len(maps[0])+2)]]
    [newmap.append([0] + x + [0]) for x in maps]
    newmap.append([0 for _ in range(len(maps[0])+2)])    
    
    path = go_to_dest((1,1), newmap, destination, 1, -1)
    
    return path

정확성 만점인데 효율성 0점인 거 실화냐고요 ...

그도 그럴것이.. DFS 라는 것은 모든 경로를 탐색한 후에 min path 값을 내놓기 때문이다

path 계산 중에 minpath 보다 높아지면 반환되도록 Backtracking을 구성했는데도...

생각해보면 당연하다ㅎ

가능한 모든 경우의 path를 찾은 후 최소 path를 반환하는 것이나 마찬가지니까!!!

한 경로 끝까지 탐색 후 --> 다음 경로 탐색.. 이게 아니라

BFS로 여러 경로를 한번에 퍼지듯이 훑어야 했다

 

 

2. BFS (정답)

from collections import deque

def solution(maps):  
    # out of range 방지 위해서, map의 가장자리에 0을 붙임  
    row, col = len(maps), len(maps[0])
    dest = (row-1, col-1)
    path = -1
    q = deque([(0,0,1)])  # start from (0,0), path_count = 1  
    
    xs = [-1, 1, 0, 0]
    ys = [0, 0, -1, 1]

    while q:
        #큐에서 좌표 뽑아서 현재 좌표 방문
        (now_x, now_y, now_path) = q.popleft()
        
        #무시 조건: 0일 시 (벽일 시) continue - 이거 안해주면 효율성 시간초과남
        if maps[now_x][now_y] == 0:
            continue
            
        #종료 조건: 목적지에 도착 시 return
        if (now_x, now_y) == dest:
            return now_path
    
        #상하좌우로, 아직 방문하지 않은 좌표 찾아 방문할 수 있도록 큐에 추가
        maps[now_x][now_y] = 0
        for x,y in zip(xs, ys):
            next_x, next_y = now_x+x, now_y+y
            if 0 <= next_x < row and 0 <= next_y < col: 
                q.append((next_x, next_y, now_path+1))  
                #현재 좌표의 최단거리+1 과 dict에 있는 경우 그 값을 비교해서 Minimum 값을 구해도 되지만, 
                #짧은 거리일수록 먼저 그 좌표에 도달할 것이므로 그냥 +1 
                
    return path

힘겨웠다... 질문의 힘도 많이 빌림 ^^

BFS로 고쳤는데도 효율성에서 0점이 나왔다.

이게 뭐지 ? 싶어서

1) map 가장자리에 0 추가하는 것 뺌

2) path 값을 따로 저장했었는데, 그냥 큐에 같이 저장하도록 함

3) 쓸데없는 변수 모두 지우고 최대한 간소화

했는데도 0점이 나왔다.

 

1시간 고민끝에 질문하기를 보다가... 도대체 내 코드랑 다른 점이 없어서 또 한참을 헤맸다 ㅎ...

알고보니 문제는 "무시조건"을 지정해주지 않은 것에 있었음

 

좌표 꺼내고 보니 만약 방문했다면 continue한다 <-- 이걸 넣어주지 않았더니, 방문했던 곳을 또 다시 거치게 되던 것이었다

ex) 큐에 만약 (1,2) (2,1) (2,2) 가 있었을 경우 (그리고 그 셋이 벽이 아닐 경우)

1. (1,2) 방문 시 (2,2) 가 다시 큐에 들어온다.

2. 큐는 (2,1) (2,2) (2,2) 가 되고

3. (2,1) 방문 시 (2,2) 는 또 큐에 들어온다.

 == 큐에 반복적으로 같은 좌표가 들어갔을 때, 이걸 바로바로 걸러낼 수 있어야 하는데 for문을 타게끔 만든 것이 화근..!!

 

많이 배운 문제였다.

내일은 문제 안 풀어도 될 듯..ㅎㅎ...ㅎㅎ.... ㅋㅋ...

 

DFS
- Stack, 재귀함수
- 가능한 모든 경우의 수를 모두 탐색해야 할 때 사용
- DFS에서의 Backtracking: 가지치기를 통해 가능성이 있는 노드만 방문 (해가 아닐 시 바로 중단시키는 방법)
- 경로의 조건 저장이 필요한 문제(경로에 어떤 게 있으면 안된다 등의 조건 있을 시 사용)
- 최적화 문제, 결정 문제 (Yes, No)

BFS
- Queue
- 가까운 정점을 먼저 방문
- 최단 거리 문제, 인접 노드 문제, 모든 정점 방문하는 문제