[프로그래머스] 게임 맵 최단거리 (문제 설명, 해결 과정, 코드 전문, c++)
| 문제 설명 |
본 문제는 프로그래머스의 게임 맵 최단거리 문제입니다.
입출력 예
| maps | answer | ||||||
| {{1,0,1,1,1}, {1,0,1,0,1}, {1,0,1,1,1}, {1,1,1,0,1}, {0,0,0,0,1}} | 11 | ||||||
| {{1,0,1,1,1}, {1,0,1,0,1}, {1,0,1,1,1}, {1,1,1,0,0}, {0,0,0,0,1}} | -1 | ||||||
| 해결 과정 |
최단거리를 구하는 문제입니다. 모든 거리는 통과하는데 드는 비용이 1로 같으니 BFS를 통해서 구할 수 있습니다.
DFS로도 구할 수는 있지만 기법의 특성 상 최선의 경우를 따졌을 때 BFS보다 느립니다.
BFS기법을 풀어 말하자면 지나온 장소는 마킹을 하여 다시 돌아오는 일을 막고 매 순간 갈 수 있는 모든 방향으로 나아갑니다. 갈 수 있는 모든 방향으로 나아가기에 퍼저나간 다양한 방향 중 하나라도 목적지에 먼저 도달한다면
그것이 최단거리가 되겠습니다.
| 코드 전문 |
// BFS
#include<vector>
#include <queue>
using namespace std;
struct pos
{
int y;
int x;
pos(int _y, int _x) {y=_y; x=_x;}
};
int solution(vector<vector<int> > maps)
{
int n = maps[0].size();
int m = maps.size();
vector<vector<bool>> visited(m, vector<bool>(n));
vector<vector<int>> min_dist(m, vector<int>(n));
queue<pos> q;
vector<int> y_dir {-1, 0, 1, 0};
vector<int> x_dir { 0, 1, 0, -1};
q.push(pos(0, 0));
visited[0][0] = 1;
min_dist[0][0] = 1;
while (!q.empty())
{
pos p = q.front();
q.pop();
int next_y;
int next_x;
for (int i=0; i<4; i++)
{
next_y = p.y+y_dir[i];
next_x = p.x+x_dir[i];
if (next_y < 0 || next_x < 0 || next_y >= m || next_x >= n) continue;
if (visited[next_y][next_x] == 1) continue;
if (maps[next_y][next_x] == 0) continue;
q.push(pos(next_y, next_x));
visited[next_y][next_x] = 1;
min_dist[next_y][next_x] = min_dist[p.y][p.x] + 1;
if (next_y == m-1 && next_x == n-1) return min_dist[next_y][next_x];
}
}
return -1;
}
// DFS 효율성 실패.
#include <vector>
#include <algorithm>
#define XPOS first
#define YPOS second
using namespace std;
int x_dir[4] = { 1,-1, 0, 0 };
int y_dir[4] = { 0, 0, 1, -1 };
vector<int> vec_shrt_path;
void dfs(vector<vector<int>> m, pair<int, int> pos, vector<vector<int>> visited, int cur_leng)
{
if (pos.XPOS == 4 && pos.YPOS == 4) vec_shrt_path.emplace_back(++cur_leng);
if (pos.XPOS >= 0 && pos.YPOS >= 0 && pos.XPOS < 5 && pos.YPOS < 5 && visited[pos.XPOS][pos.YPOS] == 0 && m[pos.XPOS][pos.YPOS] == 1)
{
int cur = ++cur_leng;
visited[pos.XPOS][pos.YPOS] = 1;
dfs(m, make_pair(pos.XPOS + x_dir[0], pos.YPOS + y_dir[0]), visited, cur);
dfs(m, make_pair(pos.XPOS + x_dir[1], pos.YPOS + y_dir[1]), visited, cur);
dfs(m, make_pair(pos.XPOS + x_dir[2], pos.YPOS + y_dir[2]), visited, cur);
dfs(m, make_pair(pos.XPOS + x_dir[3], pos.YPOS + y_dir[3]), visited, cur);
}
vec_shrt_path.emplace_back(-1);
}
int solution(vector<vector<int> > maps)
{
int answer = 0;
vector<vector<int>> visited(maps.size(), vector<int>(maps[0].size(), 0));
pair<int, int> dir = make_pair(0, 0);
dfs(maps, dir, visited, 0);
sort(vec_shrt_path.begin(), vec_shrt_path.end());
if (vec_shrt_path.back() == -1) return -1;
vec_shrt_path.erase(remove_if(vec_shrt_path.begin(), vec_shrt_path.end(), [](int i) -> bool
{return i == -1; }), vec_shrt_path.end());
answer = vec_shrt_path.front();
return answer;
}
| 느낀 점 (잡설 99% , 배운점 1%(많은 편)) |
DFS와 BFS의 얕은 지식만 있었기에 처음 DFS로 풀고 최단거리는 BFS로 풀어야한다는 이야기를 들었습니다.
두 기법 모두 흥미로웠습니다. DFS는 최단거리를 구하기 위해 모든 경우를 다찾아야만 답이 검증되는 반면
BFS는 목적지에 하나라도 도달한다면 답임을 검증 받을 수 있었습니다. 가중치 그래프라는 것에 대해서도 들었습니다. 재밌네요. 아직 이차원배열에서만 그래프탐색을 써보았기에 진짜배기 그래프문제를 접하게 되면 어떻게 해야할까 생각이 들었습니다. 이외에도 다익스트라, 벨멘 포트 알고리즘 등이 있다는걸 알았습니다. 공부할 게 많네요.
시간은 없고.
두 기법의 구조상
BFS는 큐와 중복체크배열 그리고 반복문으로 구성되었습니다. 반복문의 내부에서 인덱스 유효성과 각 종 조건문을 다루었습니다.
DFS는 재귀로 구현하였습니다. 재귀가 되니 스택으로도 되겠군요. 인접행렬로도 크기가 작을 땐 구현할 수 있다는데 말부터 어렵습니다. DFS의 패러미터로는 눈여겨 볼게 중복체크배열과 다음 좌표 현재 루트의 결과를 담고있을 변수 정도로 기억하겠습니다. DFS의 조건문 또한 목적조건일 시의 return, 인덱스 유효조건문, 중복체크 등이 있었습니다.
그리고 x좌표 y좌표에 대한 혼동도 슬슬 자리를 잡혀갑니다.
긴 글 읽어주셔서 감사합니다.
부족한 점이 있다면 부디 알려주시면 감사하겠습니다.