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

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

코딩테스트 연습 - 게임 맵 최단거리

---

1) 풀이

요즘 BFS, DFS 문제를 백준에서 집중적으로 다시 풀어보다가,

프로그래머스에서는 한 번도 이 알고리즘문제를 풀어본 적이 없어서 풀어보았다!

 

사실 기존의 BFS 풀이랑 별반 다를 건 없는데,

백준과 푸는 방식? 제출 방식? 뭐라고 해야 하나.

아무튼.. 그게 달라서 적응이 좀 필요할 것 같다 😂

 

푸는 방법자체는 아래의 글과 같으니 참고 바람!

2021.06.01 - [알고리즘 | 자료구조/백준] - [백준/c++] 2178 - 미로 탐색

[백준/c++] 2178 - 미로 탐색

2) 최종 소스코드

#include<vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
int arr[102][102]; //도착하는 칸 거리 
int tx[4]={0,1,0,-1}; //상하좌우 X 좌표
int ty[4]={1,0,-1,0}; //상하좌우 Y좌표
int solution(vector<vector<int> > maps)
{
    int answer = 0;
    memset(arr,-1,sizeof(arr)); //-1로 거리 배열 초기화
    queue<pair<int,int>>q; //탐색 좌표 담을 QUEUE
    q.push({0,0});
    arr[0][0]=1; // 첫칸을 포함하므로 첫칸을 1로 초기화
    while(!q.empty()){
        pair<int,int>cur=q.front();
        q.pop();
        for(int k=0;k<4;k++){
            int dx=cur.first+tx[k];
            int dy=cur.second+ty[k];
        if(dx<0||dx>=maps.size()||dy<0||dy>=maps[0].size()) continue;
        if(arr[dx][dy]>=0||maps[dx][dy]==0) continue;
            q.push({dx,dy});
            arr[dx][dy]=arr[cur.first][cur.second]+1;
        }
    }
    answer=arr[maps.size()-1][maps[0].size()-1]; //제일 끝 칸이 곧 몇개 칸을 지나서 왔는지
    return answer;
}

3) 참고자료