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

 

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

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

글쓴이의 답

개인적인 풀이 임으로

이것보다 더 좋은 알고리즘은 많음...

이렇게도 풀이하는구나.. 공유하기 위해 올림...

이 문제를 처음에는 DFS로 풀이했는데

DFS로는 시간초과가 발생함

이 문제는 무조건 BFS로 풀이해야함

나는 DFS로 모든 문제를 풀이할 수 있을 줄 알았는데 

이러한 문제 때문에 DFS, BFS를 적절할 때 사용할 줄 알아야하는구나 깨달았음...

#include <vector>
#include <queue>
#include <utility>
#include <iostream>
#include <iomanip>
using namespace std;


int moveY[4] = { 1,0,-1,0 };
int moveX[4] = { 0,1,0,-1 };

int bfs(queue<pair<int, int>> &bfsQ, vector<vector<int>> &maps, vector<vector<int>> &checkM){
    
    while(false == bfsQ.empty()){
        
        pair<int, int> temp = bfsQ.front();
        bfsQ.pop();
        
        for (int i = 0; i < 4; i++) {
            int nextY = temp.first + moveY[i];
            int nextX = temp.second + moveX[i];
            if ((0 > nextY) || (maps.size() <= nextY)) {
                continue;
            }
            if ((0 > nextX) || (maps[0].size() <= nextX)) {
                continue;
            }
            if ((0 == maps[nextY][nextX]) || (-1 != checkM[nextY][nextX])) {
                continue;
            }
            checkM[nextY][nextX] = checkM[temp.first][temp.second] +1; 
            bfsQ.push({nextY, nextX});
        }
    }
    return 0;
}

int solution(vector<vector<int>> maps)
{
    int answer = 0;
    
    int Ysize = maps.size();
	int Xsize = maps[0].size();
    
    vector<vector<int>> checkM(Ysize, vector<int>(Xsize, -1));
	int count = 1;
    queue<pair<int, int>> bfsQ;
    
	checkM[0][0] = 0;
    bfsQ.push({0,0});
    
    bfs(bfsQ, maps, checkM);   
    
    
    if(-1 == checkM[Ysize-1][Xsize-1]){
        answer = -1;
    }
    else{
        answer = checkM[Ysize-1][Xsize-1] +1;
    }   
    return answer;
}

 

 

참고 DFS를 사용해서 풀이한 것

이 코드를 사용하면 시간 초과가 발생함

#include <vector>
#include <queue>
#include <utility>
#include <iostream>
#include <iomanip>
using namespace std;

int dfs(vector<vector<int>> &maps, vector<vector<bool>> &checkM, int locationY, int locationX, int count, int &answer) {
	if ((maps.size()-1 == locationY) && (maps[0].size()-1 == locationX)) {
		if (count < answer) {
			answer = count;
		}
		return 0;
	}

	for (int i = 0; i < 4; i++) {
		int nextY = locationY + moveY[i];
		int nextX = locationX + moveX[i];
		if ((0 > nextY) || (maps.size() <= nextY)) {
			continue;
		}
		if ((0 > nextX) || (maps[0].size() <= nextX)) {
			continue;
		}
		if ((0 == maps[nextY][nextX]) || (true == checkM[nextY][nextX])) {
			continue;
		}
		checkM[nextY][nextX] = true;
		count++;
		dfs(maps, checkM, nextY, nextX, count, answer);
		count--;
		checkM[nextY][nextX] = false;
	}
	return 0;
}


int solution(vector<vector<int> > maps)
{
	int answer = 9999999;

	int Ysize = maps.size();
	int Xsize = maps[0].size();
    
	vector<vector<bool>> checkM(Ysize, vector<bool>(Xsize, false));
	int count = 1;
	checkM[0][0] = true;
	dfs(maps, checkM, 0, 0, count, answer);

	if (9999999 == answer) {
		answer = -1;
	}

	return answer;
}

꾸준히 하다보면 실력이 늘겠지..