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

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

 

문제

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

프로그래머스

 

분류

level2

accepted

 

풀이

최단거리 = BFS, 큐 활용

 

문제

❌ 나의 풀이

def bfs(R, C, r,c, maps):
    dr = [-1,0,1,0]
    dc = [0,1,0,-1]
    queue = [(r, c, 1)] # row, cloumn, distance
    
    while queue:
        cur_r, cur_c, distance = queue.pop(0)
        maps[cur_r][cur_c] = 'v' # visited
        
        if cur_r == R-1 and cur_c == C-1:
            return distance
        for i in range(4):
            next_r, next_c = cur_r + dr[i], cur_c + dc[i]
            if 0 <= next_r < R and 0 <= next_c < C and maps[next_r][next_c] == 1:
                queue.append((next_r, next_c, distance+1))
    return -1      

def solution(maps):
    
    answer = bfs(len(maps), len(maps[0]), 0, 0, maps)
    
    return answer

효율성 검사 불통!!

 

원인이 되는 코드

 maps[cur_r][cur_c] = 'v' # visited

문자(2byte)와 숫자(1byte)를 비교하는게 비효율적

 

cur_r, cur_c, distance = queue.pop(0)

list의 첫번째 요소를 빼면 뒤에 있는 요소들이 모두 이동해 비효율적

deque를 사용해 popleft()해주는게 더 좋다.

 

✅ 제출 코드1

from collections import deque

def bfs(R, C, maps):
    dr = [-1, 0, 1, 0]
    dc = [0, 1, 0, -1]
    queue = deque([(0, 0, 1)]) # row, cloumn, distance
    visited = [[False for _ in range(C)] for _ in range(R)]

    while queue:
        cur_r, cur_c, distance = queue.popleft()
        
        if cur_r == R-1 and cur_c == C-1:
            return distance

        for i in range(4):
            next_r, next_c = cur_r + dr[i], cur_c + dc[i]
            if 0 <= next_r < R and 0 <= next_c < C and not visited[next_r][next_c] and maps[next_r][next_c] == 1:
                visited[next_r][next_c] = True
                queue.append((next_r, next_c, distance+1))

    return -1

def solution(maps):
    answer = bfs(len(maps), len(maps[0]), maps)
    return answer

 

✅ 제출 코드2

from collections import deque

def bfs(R, C, r,c, maps):
    dr = [-1,0,1,0]
    dc = [0,1,0,-1]
    queue = deque([(r, c, 1)]) # row, cloumn, distance
    visited = [[False for _ in range(C)] for _ in range(R)]
    
    while queue:
        cur_r, cur_c, distance = queue.popleft()
        maps[cur_r][cur_c] = -1 # visited
        
        if cur_r == R-1 and cur_c == C-1:
            return distance
        for i in range(4):
            next_r, next_c = cur_r + dr[i], cur_c + dc[i]
            if 0 <= next_r < R and 0 <= next_c < C and maps[next_r][next_c] == 1:
                maps[next_r][next_c] = -1 # visited
                queue.append((next_r, next_c, distance+1))
    return -1      

def solution(maps):
    
    answer = bfs(len(maps), len(maps[0]), 0, 0, maps)
    
    return answer