[코딩테스트] [프로그래머스] 게임 맵 최단거리

문제

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

---

풀이

1. bfs로 상하좌우 위치 탐색하며 방문 체크 및 distance 증가하는 방식으로 코드 짬
   => 도착지로부터 멀어지는 경우의 수에도 distance가 증가하여 최단 거리 도출 실패

2. tuple로 현재 칸까지의 최단 거리를 저장해서 해결

---

코드

#include <vector>
#include <queue>
#include <tuple>
using namespace std;

int solution(vector<vector<int>> maps)
{
    int col = maps.size();
    int row = maps[0].size();

    queue<tuple<int, int, int>> bfs;
    vector<vector<bool>> visited(col, vector<bool>(row, false));

    bfs.push({ 0, 0, 1 });
    visited[0][0] = true;

    vector<int> dirX = { 1, 0, -1, 0 };
    vector<int> dirY = { 0, 1, 0, -1 };

    while (!bfs.empty())
    {
        tuple<int, int, int> current = bfs.front();
        int currentX = get<0>(current);
        int currentY = get<1>(current);
        int currentDistance = get<2>(current);
        
        bfs.pop();

        if (currentX == (row - 1) && currentY == (col - 1))
            return currentDistance;

        for (int i = 0; i < dirX.size(); i++)
        {
            int nextX = currentX + dirX[i];
            int nextY = currentY + dirY[i];

            if (nextX < 0 || nextX >= row || nextY < 0 || nextY >= col)
                continue;

            if (maps[nextY][nextX] == 0 || visited[nextY][nextX])
                continue;

            visited[nextY][nextX] = true;
            bfs.push({ nextX, nextY, currentDistance + 1 });
        }
    }

    return -1;
}

---

다른 풀이와 코드

0. tuple을 사용하지 않은 코드

1. map에 현재까지 최단거리를 기록하면 됨

#include<vector>
#include<iostream>
#include<queue>

using namespace std;

int check[101][101];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int solution(vector<vector<int> > maps)
{
    int n, m;
    n = maps.size();
    m = maps[0].size();
    queue<pair<int, int>> q;
    q.push(make_pair(0, 0));
    check[0][0] = true;

    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int i=0; i<4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(0<=nx && nx<n && 0<=ny && ny<m)
            {
                if(check[nx][ny] == false && maps[nx][ny] > 0)
                {
                    check[nx][ny] = true;
                    maps[nx][ny] = maps[x][y] + 1;
                    q.push(make_pair(nx, ny));
                }
            }
        }
    }

    int answer = 0;
    if(maps[n-1][m-1] == 1)
    {
        answer = -1;
    }
    else
    {
        answer = maps[n-1][m-1];
    }
    return answer;
}