[Python] 프로그래머스 lv.2 게임 맵 최단거리

 

문제 분석

• 두 팀으로 나눠서 진행
• 상대 팀 진영을 먼저 파괴하면 이기는 게임
• 각 팀 진영에 최대한 빨리 도착하는 것이 유리

• 갈 수 없는 길 & 갈 수 있는 길
• 한 번에 한 칸 동서남북으로 이동 가능

• 상대 팀이 다 막혀있다면 상대 팀 진영에 가지 못할 수도 있음

• 상대 팀 진영에 도착하기 위해 가야하는 최솟값 return
• 상대 팀 진영에 도착할 수 없다면 -1 return

• maps 크기 : n x m
• 0 : 갈 수 없는 자리
• 1 : 갈 수 있는 자리

• 처음 캐릭터는 좌측 상단 (1,1)에 위치 (인덱스로 하면 (0,0))
• 상대방 진영은 게임 맵 우측 하단 (n,m)에 위치 (인덱스로 하면 (n-1, m-1)

 

코드 설계

• maps 입력
• 갈 수 있는 경우는 맵 내부, 해당 자리의 값이 1인 경우

• return 조건 
  1. (n,m) 위치에 도달하는 경우 : return 현재까지 이동한 거리
  2. 전부 탐색했는데 만나지 못한 경우 : return -1
• 깊이 우선 ?  너비 우선 ?

 

정답 코드

1차 코드 - 실패

from collections import deque

def solution(maps):

    n = len(maps)
    m = len(maps[0])
    
    g = maps

    d = deque()
    v = [[False] * m for _ in range(n)]
    # 해당 인덱스의 값이 0이면 갈 수 없는 자리
    for i in range(len(maps)):
        for j in range(len(maps[0])):
            if maps[i][j] == 0:
                v[i][j] = True

    dh = [-1, 1, 0, 0]
    dw = [0, 0, -1, 1]

    d.append((0, 0, 0))
    v[0][0] = True

    while d:
        h, w, distance = d.popleft()  # 현재 위치 인덱스
        if h == n - 1 and w == m - 1:
            # 현재 위치 제외 ?
            return distance-1

        # 다음 위치로 이동할 수 있는가
        for k in range(4):
            nh = h + dh[k]
            nw = w + dw[k]
            # 1. 범위를 벗어나지 않는가
            if nh < 0 or nh >= n or nw < 0 or nw >= m:
                continue
            # 2. 이동하려는 인덱스의 값이 1인가
            if g[nh][nw] != 1:
                continue
            # 3. 이동하려는 인덱스를 아직 방문하지 않았는가 (v[i][j] == False 인가)
            if v[nh][nw]:
                continue

            distance += 1
            v[nh][nw] = True
            d.append((nh, nw, distance))

    return -1

• distance가 반복문 안에서 증가 : 이로 인해 노드에서 여러번 방문할 때 잘못된 값으로 누적될 수 있음
• distance가 각 경로별로 개별 관리되어야 함

2차

from collections import deque

def solution(maps):

    n = len(maps)
    m = len(maps[0])

    # g = []
    g = maps

    d = deque()
    v = [[False] * m for _ in range(n)]
    # 해당 인덱스의 값이 0이면 갈 수 없는 자리
    for i in range(len(maps)):
        for j in range(len(maps[0])):
            if maps[i][j] == 0:
                v[i][j] = True
            # else : 
            #     v[i][j] = False

    dh = [-1, 1, 0, 0]
    dw = [0, 0, -1, 1]

    d.append((0, 0, 1))
    v[0][0] = True
    # answer += 1

    while d:
        h, w, distance = d.popleft()  # 현재 위치 인덱스
        if h == n - 1 and w == m - 1 :
            return distance

        # 다음 위치로 이동할 수 있는가
        for k in range(4):
            nh = h + dh[k]
            nw = w + dw[k]

            # 1. 범위를 벗어나지 않는가
            if nh < 0 or nh >= n or nw < 0 or nw >= m:
                continue
            # 2. 이동하려는 인덱스의 값이 1인가
            if g[nh][nw] != 1:
                continue
            # 3. 이동하려는 인덱스를 아직 방문하지 않았는가 (v[i][j] == False 인가)
            if v[nh][nw]:
                continue

            v[nh][nw] = True
            d.append((nh, nw, distance+1))

    return -1

 

1. 

v[nh][nw] = True
d.append((nh, nw, distance+1))

vs

2. 

distance += 1
v[nh][nw] = True
d.append((nh,nw, distance))

1 :

• 이동할 때마다 현재 노드 거리 + 1의 값을 큐에 추가된다. distance의 거리가 매번 새로 계산된다.
• bfs 탐색은 큐에 담긴 각 노드의 경로가 독립적으로 유지된다.
• 따라서 경로마다 별개의 distance가 정확하게 관리된다.

 

2 : 

• distance 변수가 전역처럼 누적되며 증가한다.
• 모든 경로에서 동일한 distance 변수를 사용하기 때문에 큐에 담긴 다른 경로에도 영향을 미친다.
• 따라서 한 번 방문한 노드를 재방문하지 않는데 다른 경로에서 계산된 distance가 더해지는 즉, 불필요한 거리가 더해지는 문제가 발생한다.