[프로그래머스] DFS/BFS - 게임 맵 최단거리

 

 

 

아직 BFS가 낯설어서!

다른 분 코드 참고

from collections import deque

def solution(maps):

    # 방향 설정 : 앞,아래,뒤,위
    dx = [-1,0,1,0]
    dy = [0,1,0,-1]

    result = 0

    n = len(maps) # 행 개수
    m = len(maps[0]) # 각 열마다 몇 개 있는 지,

    ck = [[0]*m for _ in range(n)] # n*m 2차원 배열 생성
    dis = [[0]*m for _ in range(n)] # n*m 2차원 배열 생성
    queue = deque() # 큐 생성

    ck[0][0] = 1 #방문처리
    dis[0][0] = 1 #방문처리
    queue.append((0,0)) #큐에 삽입

    while queue:
        now = queue.popleft() # 값(0,0) 덜어내기

        for i in range(4): # 빼낸 값 기준으로 4가지 방향 설정
            x = now[0]+dx[i] # x 값 설정
            y = now[1]+dy[i] # y 값 설정

            if 0<=x<=n-1 and 0<=y<=m-1: # 허용 범위 안에 있으면서
                if ck[x][y] == 0 and maps[x][y] == 1: # ck는 방문한 적이 없고, maps는 1이라면(벽이 아니라면)
                    ck[x][y] = 1 # ck 방문 처리하고
                    dis[x][y] = dis[now[0]][now[1]] + 1 # 현재 now 값 기준 + 1 해서 dis에 거리 업데이트..
                    queue.append((x,y)) # 큐에 값 추가

    result = -1 if dis[n-1][m-1] == 0 else dis[n-1][m-1] #최종 위치 값이 0이면 -1 처리, 값이 있다면 그 값으로

    return result

 

 

BFS 이용해서 푸는 문제...

 

BFS 원리

1. 시작 노드를 큐에 넣고 방문 처리하기
2. 큐에서 노드를 꺼내고(popleft()) 인접 노드 중 방문하지 않은 노드를 큐에 넣고 방문 처리하기
3. 큐에 노드가 없을 때까지 2번 과정 반복하기

어렵다 ....