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

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

프로그래머스

 

 

문제설명

 

 

링크 참고

문제 해결 방법

 

bfs를 통해 문제를 해결하였음

 

 

코드 구현

 

 

과거에 작성한 코드 

from collections import deque

def solution(maps):
    answer = 0
    # map은 2차원 배열이라고 생각하면 됨 
    n = len(maps) #가로 
    m = len(maps[0]) #세로 

    # 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
    dx = [-1, 1, 0, 0] #세로축
    dy = [0, 0, -1, 1] #가로축 
    
    def bfs(x,y):
        #큐 구현을 위해 deque라이브러리 사용
        queue = deque()
        queue.append((x,y))
        # 큐가 빌 때까지 반복하기 
        while queue:
            x, y = queue.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                # 공간을 벗어난 경우 무시
                if nx  < 0 or nx >= n or ny < 0 or ny >= m:
                    continue
                # 벽인 경우 무시
                if maps[nx][ny] == 0:
                    continue
                # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록 
                if maps[nx][ny] == 1:
                    maps[nx][ny] = maps[x][y] + 1
                    queue.append((nx, ny))
        # 가장 오른쪽 아래 까지의 최단 거리 반환 
        return maps[n-1][m-1]
    
    
    if bfs(0,0)==1:
        answer=-1
    else:
        answer=bfs(0,0)
    
    return answer

 

 

 

 

 

from collections import deque

def solution(maps):
    answer = 0
    n = len(maps) 
    m = len(maps[0]) 
    
    # 최단 거리 구하기.
    # bfs - deque
    # 1,1 부터 시작
    dx = [1, -1, 0, 0] # 동, 서, 남, 북
    dy = [0, 0, -1, 1]
    
    # 게임 맵 벗어난 길은 갈 수 없음
    queue = deque([(0, 0)])
    distance = 0
    
    visited = [[False] * n for _ in range(m)]
    visited[0][0] = True
    
    while 1:
        if len(queue) == 0: 
            break
            
        x, y = queue.popleft()
        
        if x == n-1 and y == m-1:
            check = 1
            break   
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx >= n or ny >= m or nx < 0 or ny < 0:
                continue 
            
            if maps[nx][ny] == 0:
                continue
            
            if maps[nx][ny] == 1:
                queue.append([nx, ny])
                maps[nx][ny] = maps[x][y] +1
    
    answer = maps[n-1][m-1]
    if answer == 1:
        return -1
    return answer

 

 

시간/공간 복잡도

 

 

O(N*M)

 

최적화 및 개선

 

 

.

 

어려웠던 점

 

 

가로 세로가 헷깔렸음.

예전에 풀어봤던 문제인데도 처음엔 느낌조차 없다가 점점 느낌 살아났지만, 예전에 고민했던 부분을 또 고민하며 문제를 풀었다.