[C++] 백준 2178번: 미로 탐색

문제

https://www.acmicpc.net/problem/2178

 

풀이

(1, 1)에서 (N, M)까지 가는 최단 거리를 구하는 문제였다. 

무조건 N, M까지 도달할 수 있다는 가정이 있는 문제였다. 

 

• min[x][y]에 (1, 1)에서  (x, y)위치까지 갈 수 있는 최단거리를 저장해주었다.
• 현재 위치가 (r, c)였을 때 한칸 씩 이동하면 이동거리는 min[r][c] + 1 가 된다. 
  
  
• 즉, 현재 위치에서 한칸 이동한 값이 min[x][y]보다 작으면 재귀함수를 통해 목표 지점 (N, M)까지 진행하도록 짰다.

//한번도 진행하지 않은 길이거나 길을 한칸 갔을 때 최단거리가 맞다면
if(min[x][y] == 0 || min[x][y] > min[r][c] + 1)
{
	//최단 거리를 다시 기록해주고
    min[x][y] = min[r][c] + 1;
    
    //재귀함수로 계속 진행
    maze(x, y);
}

 

 

소스

#include <iostream>
#define MAX 101
 
int min[MAX][MAX];
bool graph[MAX][MAX];
int N, M =0;
int result = 0;
 
void showGraph()
{
    std::cout << "\n = Graph = \n";
    for(int i = 1; i<=N; ++i)
    {
        for(int j=1; j<=M; ++j)
        {
            std::cout << graph[i][j] << " ";
        }
        std::cout << "\n";
    }
    std::cout << "\n";
}
 
void showMin()
{
    std::cout << "\n = Min = \n";
    for(int i = 0; i<=N; ++i)
    {
        for(int j=0; j<=M; ++j)
        {
            std::cout << min[i][j] << " ";
        }
        std::cout << "\n";
    }
    std::cout << "\n";
}
// --------------------------------
 
void maze(int r, int c)
{
    //showGraph();
    if(r== N && c == M)
    {
        return;
    }
    
    //상하좌우
    int rPos[4] = {1, -1, 0, 0};
    int cPos[4] = {0, 0, -1, +1};
    int x, y;
    for(int i =0; i<4; ++i)
    {
        x = r+rPos[i]; y = c+cPos[i];
        if(graph[x][y])
        {
            if(min[x][y] == 0 || min[x][y] > min[r][c] + 1)
            {
                min[x][y] = min[r][c] + 1;
                maze(x, y);
                //showMin();
            }
        }
    }
    
}
 
 
 
int main()
{
 
    char c;
 
    //input
    std::cin >> N >> M;
    for(int i=1; i <=N; ++i)
    {
        for(int j=1; j<=M; ++j)
        {
            if(std::cin >> c && c == '1')
            {
                graph[i][j] = true;
            }
        }
    }
    
    //solve
    min[1][1] = 1;
    maze(1, 1);
    
    std::cout << min[N][M];
    
    return 0;
}