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

전~형적인 BFS 문제.

 

 

플레이어는 맨 왼쪽 첫 위치에서 시작하여 목표지점까지 최단거리로 가야 한다.

이것을 그러면 코드로 어떻게 판단할 것이냐?

 

먼저 필요한 것은 다음과 같다:

1. 좌표를 담을 큐(Queue)

2. n x m 크기를 가지는 dist배열(어차피 최대값이 100이니까 101 * 101로 만들면 됨)

3. dist를 0으로 모두 초기화.

4. Queue.push({0, 0})

5. dist[0][0] = 1;

 

필요한 것들을 선언했다면,

일단 처음시작점에서 Queue에 해당 좌표를 담고,

상, 하, 좌, 우를 살피면서 뚫려있는 지점(맵에서 1이라는 숫자가 들어있는 칸)이 있다면 dist 배열에서 현재 위치에 들어있는 값 + 1을 해당 칸에 넣어준다.

그래놓고 while(!Q.empty())문을 돌리면서 while문이 끝났을 때 dist의 목표지점부분 값을 확인하여

값이 0이라면 -1을 리턴하고, 그렇지 않다면 해당 칸에 들어있는 값을 리턴하면 된다.

 

BFS가 처음이라면 설명이 부족했으리라 생각될텐데,

그런 분들을 위해 좀더 자세히 설명해놓은 곳을 밑에 링크로 남겨두겠다.

(BFS를 잘 설명해놓은 곳 -> https://blog.encrypted.gg/941?category=773649) 

 

정답코드:

#include <bits/stdc++.h>
using namespace std;

int board[101][101];
int dist[101][101];
int dx[4] = {0, 1, -1, 0};
int dy[4] = {1, 0, 0, -1};
queue<pair<int, int>> Q;

int solution(vector<vector<int> > maps)
{
    int answer = 0;
    for (int i = 0; i < 101; i++)
        fill(dist[i], dist[i] + 101, 0);
    for (int i = 0; i < maps.size(); i++)
        for (int j = 0; j < maps[i].size(); j++)
            board[i][j] = maps[i][j];
 
    int verticalCount = maps.size();
    int horizontalCount = maps[0].size();
    
    Q.push({0, 0});
    dist[0][0] = 1;
    while (!Q.empty())
    {
        auto cur = Q.front();
        Q.pop();
        for (int i = 0; i < 4; i++)
        {
            int nx = dx[i] + cur.first;
            int ny = dy[i] + cur.second;
            if (nx < 0 || ny < 0 || nx >= verticalCount || ny >= horizontalCount)
                continue;
            if (board[nx][ny] != 1 || dist[nx][ny] >= 1)
                continue;
            Q.push({nx, ny});
            dist[nx][ny] = dist[cur.first][cur.second] + 1;
        }
    }
    
    if (dist[verticalCount - 1][horizontalCount - 1] == 0)
        return -1;
    else
        return dist[verticalCount - 1][horizontalCount - 1];
    
    
    return answer;
}