[level 2] 게임 맵 최단거리

 문제 

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

프로그래머스

 사용 언어 

Python3

 풀이 과정 

bfs로 풀었는데 간단한 편이라서 한 번에 통과!

추가로 효율성 점수가 있었는데 이게 높은건지 낮은건지 구분이 안가서 아래에서 다른 사람들의 코드도 돌려보았다.

실수할 뻔 한 건 처음에 무조건 N * N의 정사각형으로 입력이 주어지는 줄 알았는데 조건을 다시 읽어보니 N * M으로도 제시가 될 수 있지만 예시가 정사각형 모양인 것 뿐이었다..ㅎㅎ

 

항상 입출력 조건은 꼼꼼이 읽자!

 제출 답안 

# 지나야 하는 칸의 개수의 최솟값, 도착할 수 없는 경우 -1
# 0은 벽 / 1은 길
from collections import deque

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

q = deque([(0, 0)])

def bfs(N, M, maps, visited):
    while q:
        cx, cy = q.popleft()
        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]
            # 지도 안에 있고
            if 0 <= nx < N and 0 <= ny < M:
                # 방문 안 한 길이면
                if maps[nx][ny] == 1 and visited[nx][ny] == 0:
                    visited[nx][ny] = 1
                    maps[nx][ny] = maps[cx][cy] + 1
                    q.append((nx, ny))
    # print(maps)
    return maps[N-1][M-1] if maps[N-1][M-1] != 1 else -1

def solution(maps):
    N = len(maps)
    M = len(maps[0])
    visited = [[0 for _ in range(M)] for _ in range(N)]
    visited[0][0] = 1
    answer = bfs(N, M, maps, visited)
    return answer

 

 다른 사람 코드 

1.

from collections import deque

def solution(maps):
    x_move = [1, 0, -1, 0]
    y_move = [0, 1, 0, -1]

    x_h, y_h = (len(maps[0]), len(maps))
    queue = deque([(0, 0, 1)])

    while queue:
        x, y, d = queue.popleft()

        for i in range(4):
            nx = x + x_move[i]
            ny = y + y_move[i]

            if nx > -1 and ny > -1 and nx < x_h and ny < y_h:
                if maps[ny][nx] == 1 or maps[ny][nx] > d + 1:
                    maps[ny][nx] = d + 1
                    if nx == x_h - 1 and ny == y_h - 1:
                        return d + 1

                    queue.append((nx, ny, d + 1))

    return -1

• 나는 직접 maps에다가 1씩 더해가며 지나온 칸을 표시했는데, 이 코드와 2번 코드 모두 새로운 변수에 1씩 더해 바로 return해줬다.
• 그래서 마지막 칸인지를 확인하고 바로 return! 당연히 return이 되지 못했으면 갈 길이 없다는 것이므로 while문을 나와서는 -1을 리턴한다.
• 중간에 return하기 때문에 시간이 조금 더 빠를 줄 알았는데 진짜 미미했다. 0.01ms씩 빠른 정도?

 

2.

def solution(maps):
    dir = ((0, 1), (0, -1), (1, 0), (-1, 0))
    n, m = len(maps) - 1, len(maps[0]) - 1
    distance = {}
    queue = [((0, 0), 1)]

    while queue:
        coord, l = queue.pop(0)
        if coord in distance:
            continue
        elif coord == (n, m):
            return l
        distance[coord] = l
        x, y = coord
        for d in dir:
            x2, y2 = x + d[0], y + d[1]
            if x2 >= 0 and x2 <= n and y2 >= 0 and y2 <= m:
                if maps[x2][y2] and ((x2, y2) not in distance):
                    queue.append(((x2, y2), l + 1))
    return -1

• deque를 사용하지 않았다. pop(0)을 했기 때문에 조금 더 느려질 것으로 예상.
• 특이하게 distance라는 dictionary에 좌표별 최단칸을 저장했다.
• 조금씩이지만 예상대로 제일 느렸다. 그냥 코드가 깔끔해보여서 실행해봤다.

 

출처: 프로그래머스 다른 사람의 풀이