[백준] 2178번 미로 탐색

 

 

문제

소스코드

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<queue>
constexpr int MAX_WEIGHT = 5000000;
std::vector<std::vector<int>> g_nodes;
std::vector<std::vector<int>> g_weight;
int N, M;
 
class Node {
public:
    int y_;
    int x_;
    int weight_;
    Node() = default;
    Node(int y, int x, int weight) :y_(y), x_(x), weight_(weight) {};
};
 
void BFS() {
    std::queue<Node> queue;
    queue.emplace(Node{ 0,0,1 });
    //인접노드부터 탐색하자
    //행이 바뀌어야 내려가니 y,x 순으로 하자
    while (queue.empty() == false) {
        int y = queue.front().y_;
        int x = queue.front().x_;
        int weight = queue.front().weight_;
        queue.pop();
 
        //탐색을 계속진행하면서 더 적은 가중치가 있다면 바꾼다.
        if (g_weight[y][x] > weight) {
            g_weight[y][x] = weight;
        }
        //가중치가 더 크다면 그 길로 갈필요가 있나?
        else {
            continue;
        }
 
        //왼쪽
        if (x - 1 >= 0 && g_nodes[y][x - 1] == 1 ) {
            queue.emplace(Node{ y,x - 1,weight + 1 });
        }
        //오른쪽
        if (x + 1 < M && g_nodes[y][x + 1] == 1 ) {
            queue.emplace(Node{ y,x + 1,weight + 1 });
        }
        //위
        if (y - 1 >= 0 && g_nodes[y - 1][x] == 1 ) {
            queue.emplace(Node{ y - 1,x,weight + 1 });
        }
        //아래
        if (y + 1 < N && g_nodes[y + 1][x] == 1 ) {
            queue.emplace(Node{ y + 1,x,weight + 1 });
        }
 
    }
}
 
 
int main() {
    std::cin >> N >> M;
    
    g_nodes.assign(N,std::vector<int>(M,0));
    g_weight.assign(N, std::vector<int>(M, MAX_WEIGHT));
 
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            int value;
            scanf("%1d", &value);
            g_nodes[i][j] = value;
        }
    }
 
    BFS();
 
    std::cout << g_weight[N-1][M-1] << "\n";
}

 

 

후기

이 문제를 해결하기 위한 키워드는 BFS이다.

이 문제는 BFS(Breadth First Search)로 풀 수 있는 문제이다 DFS의 경우에는 시간 초과가 걸리는 문제이다.

 

먼저 이 문제를 풀기 위해 붙여서 들어오는 입력을 scanf(%1d) 를 사용해서 한 노드에 1 혹은 0의 값이 들어갈 수 있도록 입력을 받았으며 이 내용을 바탕으로 BFS 를 실행하였다.

원래 BFS를 사용할 때 에는 가중치 대신에 방문 여부를 확인하는 배열을 사용하는데 이 문제에서는 결국 도착지점에 도착했을 때의 최소 가중치를 원하는 문제이기 때문에 가중치를 이용했다. 

중간에 가중치가 더 크다면 continue 하는 부분을 사용해서 현재 가중치보다 크다면 탐색을 중지하는 방법을 사용했다.

여기서는 방문여부 처리를 따로 안 했기 때문에 이미 탐색한 부분도 탐색을 시도하지만 결국 가중치가 더 커져서 탐색을 중지한다.

 

 

출처 및 레퍼런스

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

 

관련 글

[자료구조 알고리즘/탐색 알고리즘(Search)] - 너비 우선 탐색(Breadth First Search)

[온라인 코딩/탐색(Search)] - [백준] 1260번 DFS와 BFS

[온라인 코딩/탐색(Search)] - [백준] 2606번 바이러스

[온라인 코딩/탐색(Search)] - [백준] 2667번 단지 번호 붙이기

[온라인 코딩/탐색(Search)] - [구름 IDE] 비타 알고 시즌2 친구의 친구를 사랑했네(★3)

[온라인 코딩/탐색(Search)] - [구름 IDE] 비타알고 시즌3 백신(★3)