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

11 Feb 2023 in Study on Coding Test

bfs를 활용하는 문제

정답제출코드

#include <vector>
#include <queue>

using namespace std;

int move_x[4] = {1, -1, 0, 0};
int move_y[4] = {0, 0, 1, -1};
queue<pair<int, int>> q; // 탐색 좌표 저장에 사용할 큐

int solution(vector<vector<int>> maps)
{   
    int x = 0, y = 0;
    int n, m;
    
    n = maps.size();
    m = maps[0].size();
    
    int graph[101][101] = {0};
    
    graph[0][0] = 1; // 첫 거리 기록
    q.push(make_pair(0, 0)); // 큐에 삽입
    
    while (!q.empty()) // 큐가 비어있지 않은 동안 -> 모든 좌표를 탐색할 동안
    {
        // 큐의 맨 앞좌표를 현재 좌표로 지정
        x = q.front().first;
        y = q.front().second;
        
        // 큐의 맨 앞 좌표 제거
        q.pop();
        
        // 상하좌우 인접한 좌표를 확인하는 곳.
        for (int i = 0; i < 4; i++)
        {
            // 상하좌우로 인접한 좌표
            int new_x = x + move_x[i];
            int new_y = y + move_y[i];
            
            // 인접한 좌표가 미로에 있는지, 방문했는지, 이동이 가능한지 확인.
            if ((0 <= new_x && new_x <= n-1) && (0 <= new_y && new_y <= m-1) && (graph[new_x][new_y] == 0) && maps[new_x][new_y] == 1)
            {
                q.push(make_pair(new_x, new_y)); // 조건에 맞는 인접 좌표를 queue에 삽입.
                graph[new_x][new_y] = graph[x][y] + 1; // 조건에 맞는 인접 좌표에 거리 기록
            }
        }
    }
    
    if (graph[n-1][m-1] == 0)
        return -1;
    
    return graph[n-1][m-1];
}

• 상하좌우 이동을 위해서 move_x, move_y를 설정한다.
• n과 m의 최대값은 100이므로 최대 101칸의 지도를 설정해준다.
• 101로 설정한 이유는 new_x, new_y를 설정하는 과정에서 오버플로우를 방지하기 위함.
• 조건에 맞는 좌표를 큐에 삽입하고, 거리를 기록한다.
• 한 칸의 4방향을 모두 탐색했으면 다음 칸을 탐색하기 시작한다.
• 어떤 한 칸이 부모라면 인접한 4방향 칸이 자식이 되는 개념이다.