백준 2178번 미로 탐색

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

전형적인 BFS 문제였기 때문에 큐를 이용하여 쉽게 풀 수 있는 문제였습니다.

중요한 부분은 해당 칸과 이동하는 칸을 모두 방문 표시 처리해야한 다는 점입니다.

#include <iostream>

#include <string>

#include <queue>

#include <cstring> //memset

using namespace std;

 

const int MAX = 100;

 

int N, M;

int maze[MAX][MAX];

bool visited[MAX][MAX];

 

typedef struct

{

        int y, x, pathLength; //좌표와 현재까지의 길이

}dir;

 

int minStep(int y, int x, int pathLength)

{

        queue<dir> q;

        int result = 0;

        dir start = { y, x, pathLength };

        q.push(start);

 

        while (!q.empty())

        {

                 int curY = q.front().y;

                 int curX = q.front().x;

                 int curLength = q.front().pathLength;

                 //cout << curY << " " << curX << " " << curLength << endl;

                 if (curY == N - 1 && curX == M - 1)

                 {

                         result = curLength;

                         break;

                 }

                 q.pop();

                 visited[y][x] = true;

                

                 //E

                 if (curX + 1 < M && maze[curY][curX + 1] && !visited[curY][curX + 1])

                 {

                         dir east = { curY, curX + 1, curLength + 1 };

                         visited[curY][curX + 1] = true;

                         q.push(east);

                 }

                 //W

                 if (curX - 1 >= 0 && maze[curY][curX - 1] && !visited[curY][curX - 1])

                 {

                         dir west = { curY, curX - 1, curLength + 1 };

                         visited[curY][curX - 1] = true;

                         q.push(west);

                 }

                 //S

                 if (curY + 1 < N && maze[curY + 1][curX] && !visited[curY + 1][curX])

                 {

                         dir south = { curY + 1, curX, curLength + 1 };

                         visited[curY + 1][curX] = true;

                         q.push(south);

                 }

                 //N

                 if (curY - 1 >= 0 && maze[curY - 1][curX] && !visited[curY - 1][curX])

                 {

                         dir north = { curY - 1, curX, curLength + 1 };

                         visited[curY - 1][curX] = true;

                         q.push(north);

                 }

        }

        return result;

}

 

int main(void)

{

        cin >> N >> M;

        for (int i = 0; i < N; i++)

        {

                 string temp;

                 cin >> temp;

                 for (int j = 0; j < M; j++)

                         maze[i][j] = temp[j]-'0';

        }

 

        memset(visited, false, sizeof(visited));

        cout << minStep(0, 0, 1) << endl; //(0, 0)도 포함

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~