[DFS/BFS]게임 맵 최단거리
** 알게 된 내용
1) 그래프 순회 문제를 풀때, 최단 거리를 알기 위해선 BFS로 문제를 해결해야한다.
- DFS는 단순히 깊이를 우선으로 탐색하기 때문에, 모든 경로를 탐색하면서도 최단 경로를 보장 할 수 없다.
BFS의 경우 탐색할떄 거리가 짧은 경로부터 차례로 탐색하기 때문에 도착점에 처음 도착한 순간이 곧 최단거리이다.
< 문제 >
캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.
게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요.
단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.
* 제한사항
- maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
- n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
- maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
- 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.
< 해결방법 >
1. 최단거리 판단 방법 찾기.
- 동적 계획법으로 풀이
- BFS로 풀이
int solution(vector<vector<int>> maps)
{
int res;
int cols = maps.size();
int rows = maps[0].size();
vector<int> dx {1,-1,0,0};
vector<int> dy {0,0,1,-1};
vector<vector<int>> dist (cols,vector<int>(rows,-1));
vector<vector<bool>> visited (cols,vector<bool>(rows,false)); // #1
queue<pair<int,int>> q;
q.push({0,0});
dist[0][0]=1;
while(!q.empty())
{
auto [x,y] = q.front();
q.pop();
if(x==cols-1&&y==rows-1) // #2
break;
//동서남북으로 이동하기.
for(int i=0;i<4;i++)
{
int x_nxt=x+dx[i];
int y_nxt=y+dy[i];
if(x_nxt<0||y_nxt<0||x_nxt>=rows||x_nxt>=cols) continue;
if(maps[x_nxt][y_nxt]==0||dist[x_nxt][y_nxt]!=-1) continue;
dist[x_nxt][y_nxt]=dist[x][y]+1;
q.push({x_nxt,y_nxt});
}
}
return dist[cols-1][rows-1];
}
#1 기존 BFS 진행시 visited 변수로 해당 노드에 방문 여부를 파악했다.
위의 문제는 dist 변수로 방문여부를 파악하기에 visited 변수를 추가 선언하여 사용할 필요가 없다.
#2 BFS의 최종 목적지는 m-1,n-1이 아니라, 가장 깊은 레벨의 노드다.
따라서 queue를 끝까지 다 돌리더라도, m-1,n-1은 해당 노드에 도착하는 최소거리가 되기에 해당 조건을 없애도 된다.
**01.06 재 풀이
코드
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define DIRECTION_NUM 4
int solution(vector<vector<int>> maps)
{
if (maps.empty() || maps[0].empty()) {
return -1;
}
int res;
vector<int> dx {1,-1,0,0};
vector<int> dy {0,0,1,-1};
int m = maps.size();
int n = maps[0].size();
vector<vector<int>> dist(m,vector<int>(n,-1));
//1. 초기화
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(maps[i][j]==0)
dist[i][j]=0;
}
}
queue<pair<int,int>> q;// 좌표를 인가.
q.push({0,0});
dist[0][0]=1;
while(!q.empty())
{
//2. pop 하여 현재 위치의 거리 업데이트
auto [cur_y,cur_x] = q.front();
q.pop();
if(cur_y==m-1&&cur_x==n-1)
break;
//3. 이동시키며 이동 가능 확인 진행. -> 이동 불가한 경우 예외처리 필요.
for(int i=0;i<DIRECTION_NUM;i++)
{
int x = cur_x +dx[i];
int y = cur_y +dy[i];
// dist가 -1이고, map이 1인경우.
//이때, dist값을 업데이트 해야함. -> 배열이 오버플로우
if(x>=0&&y>=0&&x<n&&y<m&&maps[y][x]==1&&dist[y][x]==-1)//**오답 1 if(maps[y][x]==1&&dist[y][x]==-1)
{
q.push({y,x});
dist[y][x] = dist[cur_y][cur_x]+1;//**오답 dist[y][x] = cur_dist+1;
}
}
}
//4. 도달 했으면 m-1,n-1 값 리턴
// 못했을 시 -1 리턴.
if(dist[m-1][n-1]==-1)
res = -1;
else
res = dist[m-1][n-1];
return res;
}<오답 내용>
1) 배열의 오버플로우 고려 부족
- 반복문 내에서 배열을 확인하는 경우, 오버플로우되지 않도록 범위를 설정해 줘야한다.
[추후 개념화 과정시 FLOW]
1) 주어진 조건에 따라 증감되도록 idx 변경
2) 배열에서 비교 전, 해당 idx가 배열의 오버플로우를 일으키지 않도록 조건 추가
3) 비교 진행
2) 개념화 부족 (좌표별 지나온 거리변수 업데이트 에러)
- 현재 좌표거리를 선언하고, 해당 값을 동작 케이스별 업데이트 하지 않았다.
=> 따라서 현재 좌표거리가 현재 좌표거리로서 사용되지 못하고, 첫 좌표거리로 사용됐다.
- 좌표별 지나온 거리 변수 dist 배열은 언제 업데이트 되야하는가?
- 동작을 정확히 정의하고 작업을 진행해야한다.
[추후 개념화 과정시 FLOW]
- 개념 명확화 진행.
< 동작 >
1) 현재 위치 확인( 이미 접근 가능여부 확인된 좌표 )
2) 현재 좌표에서 이동가능한 인접 좌표 확인
3) 이동 가능한 인접 좌표를 큐에 push& 해당 인접 좌표의 지나온 거리 변수 업데이트( 현재 좌표 거리 +1 )
-> 현재 좌표거리는 현재좌표거리 변수를 사용해야함.
#3차
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int solution(vector<vector<int>> maps)
{
int answer;
int x_max = maps[0].size();
int y_max = maps.size();
vector<vector<int>> dist(y_max,vector<int>(x_max,0));
vector<int> dx {0,0,1,-1};
vector<int> dy {1,-1,0,0};
queue<pair<int,int>> q;
q.push({0,0});
dist[0][0]=1;
while(!q.empty())
{
auto [cur_y,cur_x] = q.front();
q.pop();
if(cur_y==y_max-1&&cur_x==x_max-1)
break;
for (int i = 0; i < 4; i++)
{
int x = cur_x + dx[i];
int y = cur_y +dy[i];
if(x<0||y<0||x>=x_max||y>=y_max) continue;
if(maps[y][x]==1&&dist[y][x]==0)
{
dist[y][x]=dist[cur_y][cur_x]+1;
q.push({y,x});
}
}
}
if(dist[y_max-1][x_max-1]==0)
return -1;
else
return dist[y_max-1][x_max-1];
}
- dist 변수를 visited 변수용으로 사용하고, 벽 확인용은 maps 변수를 사용하여 풀이한다.