미로 탐색 [C++]

문제 링크: https://www.acmicpc.net/problem/2178

난이도: ⚪

문제 설명

문제 접근

1. 그래프의 좌푯값이 1인 지점은 연결되어 있기 때문에 BFS를 이용하여 최단 거리를 갱신한다.
2. BFS를 구현할 때, [상, 하, 좌, 우]가 연결되어 있는지 확인한다.
3. 인덱스 에러가 나지 않도록 탐색 범위를 정해줘야 한다.
   
   

제출 코드

#include<iostream>
#include<string>
#include<vector>
#include<queue>
using namespace std;

// 주어진 미로 maze와 거리를 갱신할 dis, 방문을 확인할 visited배열 선언.
int maze[101][101]{ 0 };
int dis[101][101]{ 1 };
bool visited[101][101]{};

// BFS 구현
void Search(pair<int, int> node)
{
	// 시작 지점(node)을 큐에 넣는다.
    visited[node.first][node.second] = true;
    queue<pair<int, int>> q;
    q.push(node);

    // 상 하 좌 우
    int dy[4]{-1, 1, 0, 0};
    int dx[4]{0, 0, -1, 1};
	
    // 큐가 비워질 때까지 반복한다.
    while (!q.empty())
    {
        pair<int, int> cur_node = q.front();
        int y = cur_node.first;
        int x = cur_node.second;
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
			
            // 인덱스의 범위를 정해준다. 
            if(ny >= 0 && nx >= 0 && ny < 101 && nx < 101)
            {
            	// 방문의 여부와 이동할 수 있는 칸인지 확인한다.
                if (!visited[ny][nx] && maze[ny][nx] == 1)
                {
                    dis[ny][nx] = dis[y][x] + 1;
                    visited[ny][nx] = true;
                    
                    // 확인후 큐에 넣는다.
                    q.push(make_pair(ny, nx));
                }
            }
        }
    }
}

int main(void)
{
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        string temp;
        cin >> temp;
        for (int j = 0; j < M; j++)
            if (temp[j] == '1')
                maze[i][j] = 1;
    }

    pair<int, int> start = make_pair(0, 0);
    Search(start);
    cout << dis[N - 1][M - 1];
    return 0;
}

결과