미로 탐색 (Silver 1)
문제
2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net
접근법
이 문제에서 구해야 하는 값은 미로를 탈출하기 위해 필요한 최단경로의 길이이다. 최단 경로의 길이를 구하기 위해서는 DFS보다 BFS를 활용해야 한다. 너비 우선으로 탐색하는 BFS에서 탐색 깊이는 항상 최단거리를 보장하기 때문이다. 하지만 DFS는 최단 경로를 보장하기보단 하나의 경로를 끝까지 탐색하기 때문에 최단경로를 두고 다른 경로로 탐색을 완료할 위험이 있다. 아래와 같은 상황을 살펴보자.
이 미로에서는 위에 초록색 경로가 최단 경로이며 최단 경로 길이로 9가 나와야 한다. 하지만 DFS로 탐색을 진행할 경우 아래와 같이 최단경로가 아닌 길을 따라가는 문제가 발생할 수도 있다.
그래서 이번 문제와 같이 최단경로의 길이를 구해야할 때는 DFS보다는 BFS가 더 효과적이다. 그래서 BFS를 구현하여 문제를 해결해 보자.
자료구조 선택
먼저 Node에 어떤 정보가 필요한가를 살펴보자. 각 노드에는 현재 탐색 깊이에 대한 정보가 필요하다. 탐색 깊이가 곧 미로에서 이동한 거리가 된다. 그리고 BFS를 구현하기 위해서는 각 노드별 방문 기록을 확인할 bool 타입 변수와 그리고 해당 노드가 목표노드인지 아닌지에 대한 bool타입 변수가 필요하다. 마지막으로 각 노드의 인접 노드에 대한 정보가 필요하다. 인접 노드는 상하좌우 최대 4개이기 때문에 배열을 활용하려고 한다. 그래서 아래와 같이 노드를 선언하고, 미로의 지도를 선언한다.
struct Node {
Node() : depth(0), isVisited(false), isTarget(false), adjacent{} {}
int depth;
bool isVisited;
bool isTarget;
array<Node*, 4> adjacent;
};
using NodeMap = array<array < Node*, 100>, 100>;기능 구현
문제를 풀기 위해서 필요한 기능을 정리하면 다음과 같다.
- 문제로 부터 데이터를 입력받는다.
- 각 노드들의 인접 노드를 설정한다.
- BFS 탐색을 통해서 최단거리를 구한다.
- (필요에 따라서) 동적으로 할당한 노드를 해제한다.
해당 기능들을 캡슐화하여 구현하기 위해서 Maze 클래스를 만다.
클래스 정의
다음으로 미로를 클래스로 정의하여서 데이터를 입력받는 기능, 인접 노드를 연결하는 기능, 목표지점을 탐색하는 기능, 노드를 삭제하는 기능을 캡슐화하자. Maze 클래스를 다음과 같이 선언하였다.
class Maze {
public:
Maze(int _N, int _M) : N(_N), M(_M), map{}
{}
~Maze();
void InputData(); // 미로 정보를 입력받는다.
void ConnectAdjacent(); // 인접노드를 연결한다.
int Search(); // BFS 탐색을 하고 최단 거리를 반환한다.
private:
NodeMap map;
int N, M;
};이렇게 선언한 Maze 클래스는 main함수에서 다음과 같이 활용할 예정이다.
int main()
{
int N, M;
cin >> N >> M;
Maze maze(N, M);
maze.InputData(); // 데이터 입력
maze.ConnectAdjacent(); // 인접노드 설정
cout << maze.Search(); // BFS로 이동거리 탐색
// ~Maze() 호출 동적할당한 노드 삭제
return 0;
}이제 각 기능별로 나눠진 멤버함수를 정의하자.
데이터 입력
Maze::InputData함수에서는 문제의 미로 데이터를 입력받는다. 입력값이 0인 노드로는 이동할 필요가 없고, 그래서 연결할 필요도 없다. 굳이 사용하지 않는데 노드를 만들 필요도 없기 때문에 입력값이 1인 위치에만 노드를 생성해 주자. 그리고 마지막 (N, M) 노드가 목표지점임을 inTarget 멤버변수에 마킹하자.
void Maze::InputData()
{
for (int i = 0; i < N; ++i)
{
string row;
cin >> row;
for (int j = 0; j < M; ++j)
{
if (row[j] == '1') // 값이 1인 위치에만 노드를 생성한다.
map[i][j] = new Node();
}
}
map[N - 1][M - 1]->isTarget = true;
}인접 노드 연결
앞서 데이터를 입력받을 때 값이 0인 위치에는 노드를 생성하지 않았기 때문에 nulltpr이다. 따라서 map[i][j]처럼 인덱싱을 하기 전에 해당 노드가 nullptr인지 확인해야 한다. 그리고 유효한 노드일 경우 상하좌우에 노드가 존재한다면 인접 노드 배열 adjacent에 추가한다.
void Maze::ConnectAdjacent()
{
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < M; ++j)
{
if (map[i][j] == nullptr) continue;
if (i > 0)
{
if (map[i - 1][j])
map[i][j]->adjacent[0] = map[i - 1][j];
}
if (i < N - 1)
{
if (map[i + 1][j])
map[i][j]->adjacent[1] = map[i + 1][j];
}
if (j > 0)
{
if (map[i][j - 1])
map[i][j]->adjacent[2] = map[i][j - 1];
}
if (j < M - 1)
{
if (map[i][j + 1])
map[i][j]->adjacent[3] = map[i][j + 1];
}
}
}
}BFS 탐색
BFS탐색은 queue가 비거나, 목표노드에 도달했을 때까지 진행한다. 인접 노드를 queue에 삽입하기 전에 깊이값을 현재 노드의 깊이 값에 +1 한 값으로 갱신하자. 그리고 목표 노드에 도달했다면 목표 노드의 깊이 값이 정답이 되기 때문에 반환하여 main함수에서 출력할 수 있도록 하자. 문제에서 탐색에 실패한 경우는 별도의 언급은 없었다. 컴파일을 위해서 실패한 경우 -1을 반환하도록 하자.
int Maze::Search()
{
queue<Node*> q;
map[0][0]->isVisited = true;
map[0][0]->depth = 1;
q.push(map[0][0]);
while (!q.empty())
{
Node* cur = q.front();
q.pop();
for (Node* nextNode : cur->adjacent)
{
if (nextNode == nullptr) continue;
if (nextNode->isVisited) continue;
nextNode->depth = cur->depth + 1;
nextNode->isVisited = true;
// 목표에 도달했을 때 깊이값 반환
if (nextNode->isTarget)
{
return nextNode->depth;
}
q.push(nextNode);
}
}
// 탐색에 실패한 경우
return -1;
}동적할당 노드 삭제
~Maze()에서 동적으로 할당한 노드를 아래와 같이 삭제하자.
Maze::~Maze()
{
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < M; ++j)
{
if (map[i][j] == nullptr) continue;
delete map[i][j];
}
}
}성능평가
이 풀이에서 시간 복잡도를 따지기 위해서 가장 시간복잡도가 높은 BFS의 이중 반복문을 살펴보자. 첫번 째 반복문 while은 중복노드에 대해서는 탐색이 진행되지 않기 때문에 전체 노드\(M \cdot N\)에 대해서 최대 한 번씩만 진행된다. while문 내부에 있는 for문은 최대 전체 간선의 수\(E\) 만큼 수행한다. 그런데 간선은 각 노드마다 4개씩 배열로 생성했기 때문에 \(E\) = \(M + N\)이다. 따라서 이 알고리즘의 시간 복잡도는 \(O(M \cdot N)\)이다. 공간 복잡도 또한 마찬가지로 \(O(M \cdot N)\) 만큼 공간이 필요하다.
전체 코드
#include <iostream>
#include <array>
#include <string>
#include <queue>
#define endl '\n'
using namespace std;
struct Node {
Node() : depth(0), isVisited(false), isTarget(false), adjacent{} {}
int depth;
bool isVisited;
bool isTarget;
array<Node*, 4> adjacent;
};
using NodeMap = array<array < Node*, 100>, 100>;
class Maze {
public:
Maze(int _N, int _M) : N(_N), M(_M), map{}
{}
~Maze();
void InputData();
void ConnectAdjacent();
int Search();
private:
NodeMap map;
int N, M;
};
int main()
{
//입출력 성능향상을 위한 설정
ios_base::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);
int N, M;
cin >> N >> M;
Maze maze(N, M);
maze.InputData(); // 데이터 입력
maze.ConnectAdjacent(); // 인접노드 설정
cout << maze.Search(); // BFS로 이동거리 탐색
// ~Maze() 호출 동적할당한 노드 삭제
return 0;
}
Maze::~Maze()
{
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < M; ++j)
{
if (map[i][j] == nullptr) continue;
delete map[i][j];
}
}
}
void Maze::InputData()
{
for (int i = 0; i < N; ++i)
{
string row;
cin >> row;
for (int j = 0; j < M; ++j)
{
if (row[j] == '1')
map[i][j] = new Node();
}
}
map[N - 1][M - 1]->isTarget = true;
}
void Maze::ConnectAdjacent()
{
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < M; ++j)
{
if (map[i][j] == nullptr) continue;
if (i > 0)
{
if (map[i - 1][j])
map[i][j]->adjacent[0] = map[i - 1][j];
}
if (i < N - 1)
{
if (map[i + 1][j])
map[i][j]->adjacent[1] = map[i + 1][j];
}
if (j > 0)
{
if (map[i][j - 1])
map[i][j]->adjacent[2] = map[i][j - 1];
}
if (j < M - 1)
{
if (map[i][j + 1])
map[i][j]->adjacent[3] = map[i][j + 1];
}
}
}
}
int Maze::Search()
{
queue<Node*> q;
map[0][0]->isVisited = true;
map[0][0]->depth = 1;
q.push(map[0][0]);
while (!q.empty())
{
Node* cur = q.front();
q.pop();
for (Node* nextNode : cur->adjacent)
{
if (nextNode == nullptr) continue;
if (nextNode->isVisited) continue;
nextNode->depth = cur->depth + 1;
nextNode->isVisited = true;
// 목표에 도달했을 때 깊이값 반환
if (nextNode->isTarget)
{
return nextNode->depth;
}
q.push(nextNode);
}
}
// 탐색에 실패한 경우
return -1;
}
