[프로그래머스] 게임 맵 최단거리 파이썬

게임 맵 최단거리 ( https://programmers.co.kr/learn/courses/30/lessons/1844 )

프로그래머스의 문제입니다. 전형적인 길 찾기 문제 유형으로 BFS로 해결할 수 있는 문제입니다. 혼자 해결하려다 진행이 되지 않아서 다른 분의 코드를 보고 이해하였고 혼자 풀어낼 수 있게 되었습니다.

문제 해결

• 입력으로 주어지는 maps와 같은 크기를 가진 check배열을 만들어 -1으로 채워줍니다.
• 상단의 dd배열을 이용하여 시작 지점인 0,0 자리부터 상하좌우 방향을 탐색하여 방문할 수 있는 곳인 1을 찾아 queue에 추가 해줍니다.
• 방문할 수 있는 곳을 찾아 해당 지점으로 이동을 하면서 check의 같은 지점에 1을 더해주어 해당 지점까지 최소 거리를 확인 해줍니다.

dd = [[1,0],[0,1],[-1,0],[0,-1]];	#상하좌우로 이동하는 동작을 편하게 하기위한 dd

def solution(maps):
    y = len(maps);			#배열의 개수를 가지고 y값을 찾아냅니다.
    x = len(maps[0]);			#배열 안의 값의 개수를 가지고 x값을 찾아냅니다.
    
    check = [[ -1 for _ in range(x) ] for _ in range(y)]; #map과 같은 크기의 check 배열을 -1으로 채워서 만들어 냅니다.
    check[0][0] = 1			#시작 지점인 0,0 에는 무조건 방문함으로 1으로 직접 입력 해줍니다.
    
    queue = []				#bfs를 실행할? queue를 만들어 줍니다.
    queue.append([0,0]);		#queue에 시작점인 0,0을 직접입력해 줍니다.
    
    while queue:			#queue에 값이 없어질 때 까지 반복합니다.
        b, a = queue.pop(0);		#queue의 값을 꺼내어와 값을 변수에 담아 줍니다.
        for i in range(4):		#네 방향을 모두 확인해 줍니다.
            dy = b + dd[i][0];
            dx = a + dd[i][1];
            
            if -1<dx<x and -1<dy<y:	#dx, dy가 map배열의 범위를 벗어나지 않는다면 확인을 시작합니다.
                if maps[dy][dx] == 1:	#maps[dy][dy]가 벽으로 막혀있지 않고(값이 1이고)
                    if check[dy][dx] == -1:	#아직 방문하지 않은 곳이라면(check[dy][dx]가 -1이라면
                        print(dy,dx)
                        check[dy][dx] = check[b][a] + 1;	#해당 위치를 방문합니다. 해당 위치는 지금 위치보다 한칸 앞으로 간 상태이므로 +1 해줍니다.
                        queue.append([dy,dx]);	#해당 위치에 방문하기 위해 queue에 담아줍니다.
                
            
    answer = check[-1][-1]; 		#위의 while문이 종료되면 도착지점의 값에 대한 최단거리 값이 나타나게 됩니다.
    return answer

=> 문제를 이해함에 따라서 bfs에 대한 개념은 알고 있었지만 x, y가 자꾸 헷갈리는 것이 가장 큰 문제였습니다. 이후 반복하여 확인하여 개념을 다지도록 해야겠습니다.

참고
study-dev347님의 블로그 - [프로그래머스] 게임 맵 최단거리(Python)