이 문제에서는 행렬 mat[][]가 주어집니다. 이 행렬은 지뢰가 매설된 경로를 나타내며, 지뢰는 값 0으로 표시됩니다. 우리의 목표는 지뢰가 있는 경로에서 가장 안전한 최단 경로를 찾는 것입니다.
안전한 경로를 따라 이동할 때는 지뢰에 인접한 칸(왼쪽, 오른쪽, 위, 아래)도 위험하므로 반드시 피해야 합니다.
경로를 탐색하는 동안 허용되는 유효한 이동은 다음과 같습니다.
- 왼쪽 : mat[i][j] => mat[i-1][j]
- 오른쪽 : mat[i][j] => mat[i+1][j]
- 위 : mat[i][j] => mat[i][j-1]
- 아래 : mat[i][j] => mat[i][j+1]
예제로 문제 이해하기
입력
mat[][] = {
{1, 1, 0, 1},
{1, 1, 0, 1},
{1, 1, 1, 1},
{1, 1, 1, 1}
}출력
가장 안전한 최단 경로의 길이는 7입니다.
설명
{
{1, 1, 0, 1},
{1, 1, 0, 1},
{1, 1, 1, 1},
{1, 1, 1, 1}
}위 예제에서 굵게 표시된 경로를 따라 이동하면 첫 번째 열에서 마지막 열까지 총 7칸을 이동하게 되며, 이것이 지뢰를 피할 수 있는 가장 짧은 안전 경로입니다.
해결 접근 방법 1: 백트래킹(Backtracking)
가장 단순한 해결 방법은 백트래킹을 사용하는 것입니다. 경로를 찾기 전에 먼저 모든 지뢰에 인접한 칸들을 위험 구역으로 표시합니다.
그다음, 시작점이 되는 첫 번째 열의 각 안전한 칸에서 출발하여 목적지(마지막 열의 임의의 칸)에 도달할 수 있는지 확인합니다. 목적지까지 도달 가능한 모든 안전한 경로 중에서 가장 짧은 경로의 길이를 찾아 반환합니다.
- 경로가 존재하면 해당 경로의 길이를 반환합니다.
- 경로가 존재하지 않으면 -1을 반환하여 경로를 찾을 수 없음을 나타냅니다.
구현 예제 코드
#include <bits/stdc++.h>
using namespace std;
#define R 11
#define C 10
int rowNum[] = { -1, 0, 0, 1 };
int colNum[] = { 0, -1, 1, 0 };
bool isSafe(int mat[R][C], int isvisited[R][C], int x, int y){
if (mat[x][y] == 0 || isvisited[x][y])
return false;
return true;
}
bool isValid(int x, int y){
if (x < R && y < C && x >= 0 && y >= 0)
return true;
return false;
}
void unSafeCellsInPath(int mat[R][C]){
for (int i = 0; i < R; i++){
for (int j = 0; j < C; j++){
if (mat[i][j] == 0){
for (int k = 0; k < 4; k++)
if (isValid(i + rowNum[k], j + colNum[k]))
mat[i + rowNum[k]][j + colNum[k]] = -1;
}
}
}
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++){
if (mat[i][j] == -1)
mat[i][j] = 0;
}
}
}
void findShortestSafeRouteRec(int mat[R][C], int isvisited[R][C], int i, int j, int &min_dist, int dist){
if (j == C-1){
min_dist = min(dist, min_dist);
return;
}
if (dist > min_dist)
return;
isvisited[i][j] = 1;
for (int k = 0; k < 4; k++){
if (isValid(i + rowNum[k], j + colNum[k]) && isSafe(mat, isvisited, i + rowNum[k], j + colNum[k])){
findShortestSafeRouteRec(mat, isvisited, i + rowNum[k], j + colNum[k], min_dist, dist + 1);
}
}
isvisited[i][j] = 0;
}
int findShortestSafeRoute(int mat[R][C]){
int minSafeDist = INT_MAX;
int isvisited[R][C];
unSafeCellsInPath(mat);
for (int i = 0; i < R; i++) {
if (mat[i][0] == 1) {
memset(isvisited, 0, sizeof isvisited);
findShortestSafeRouteRec(mat, isvisited, i, 0, minSafeDist, 0);
if(minSafeDist == C - 1)
break;
}
}
if (minSafeDist != INT_MAX)
return minSafeDist;
else
return -1;
}
int main() {
int mat[R][C] =
{
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 0, 1, 1, 1, 1, 1, 1, 0, 1 },
{ 1, 1, 1, 0, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 0, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 0, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 0, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 1, 1, 1, 1 }
};
int pathLen = findShortestSafeRoute(mat);
if(pathLen == -1)
cout<<"No Safe Path from source to destination possible!";
else
cout<<"Shortest Safe route Length is "<<pathLen;
return 0;
}
출력 결과
Shortest Safe route Length is 10
해결 접근 방법 2: 너비 우선 탐색(BFS)
대안적인 해결 방법으로 너비 우선 탐색(BFS)을 사용할 수 있습니다. 큐(queue)를 활용하여 첫 번째 열에서 마지막 열까지의 경로를 찾고, 그중 최소 거리를 반환합니다.
BFS는 모든 간선의 가중치가 동일한 그리드 문제에서 최단 거리를 보장하기 때문에, 백트래킹보다 효율적으로 최단 경로를 찾을 수 있다는 장점이 있습니다.
구현 예제 코드
#include <bits/stdc++.h>
using namespace std;
#define R 11
#define C 10
int rowNum[] = { -1, 0, 0, 1 };
int colNum[] = { 0, -1, 1, 0 };
struct Key{
int x,y;
Key(int i,int j){ x=i;y=j;};
};
bool isValid(int x, int y) {
if (x < R && y < C && x >= 0 && y >= 0)
return true;
return false;
}
int findShortestSafeRoute(int mat[R][C]){
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (mat[i][j] == 0) {
for (int k = 0; k < 4; k++)
if (isValid(i + rowNum[k], j + colNum[k]))
mat[i + rowNum[k]][j + colNum[k]] = -1;
}
}
}
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (mat[i][j] == -1)
mat[i][j] = 0;
}
}
int visited[R][C];
for(int i=0;i<R;i++){
for(int j=0;j<C;j++)
visited[i][j] = -1;
}
queue<Key> distQueue;
for(int i=0;i<R;i++){
if(mat[i][0] == 1){
distQueue.push(Key(i,0));
visited[i][0] = 0;
}
}
while(!distQueue.empty()){
Key k = distQueue.front();
distQueue.pop();
int d = visited[k.x][k.y];
int x = k.x;
int y = k.y;
for (int k = 0; k < 4; k++) {
int xp = x + rowNum[k];
int yp = y + colNum[k];
if(isValid(xp,yp) && visited[xp][yp] == -1 && mat[xp][yp] == 1){
visited[xp][yp] = d+1;
distQueue.push(Key(xp,yp));
}
}
}
int pathLen = INT_MAX;
for(int i=0;i<R;i++){
if(mat[i][C-1] == 1 && visited[i][C-1] != -1){
pathLen = min(pathLen,visited[i][C-1]);
}
}
if(pathLen == INT_MAX)
return -1;
else
return pathLen;
}
int main() {
int mat[R][C] =
{
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 0, 1, 1, 1, 1, 1, 1, 0, 1 },
{ 1, 1, 1, 0, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 0, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 0, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 0, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 1, 1, 1, 1 }
};
int pathLen = findShortestSafeRoute(mat);
if(pathLen == -1)
cout<<"No Safe Path from source to destination possible!";
else
cout<<"Shortest Safe route Length is "<<pathLen;
return 0;
}
출력 결과
Shortest Safe route Length is 10
마무리
두 가지 접근 방식 모두 지뢰와 그 인접 칸을 먼저 위험 구역으로 처리한 뒤 경로를 탐색한다는 공통점이 있습니다. 백트래킹은 구현이 직관적이지만 최악의 경우 시간 복잡도가 커질 수 있고, BFS는 큐 기반의 레벨 순회를 통해 최단 거리를 더 효율적으로 보장합니다. 실제 코딩 테스트나 알고리즘 문제 풀이에서는 BFS 방식을 권장합니다.