벽 부수고 이동하기(Gold 4)
문제
2206번: 벽 부수고 이동하기
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로
www.acmicpc.net
접근법
이번 문제는 출발 지점에서 목표지점까지의 최단거리를 구하는 문제이다. 최단 거리 문제는 DFS보다는 BFS로 풀어야 하는 문제이다. 그리고 이 문제는 벽을 한번 부수고 지나갈 수 있다는 점에서 조금 더 까다로운 문제가 된다. visited 전역 배열을 보통 2차원 배열로 많이 사용하는데 이 문제에서는 기존의 2차원 배열에 벽을 한번 부수었을 때 방문하는 경우와 벽을 한 번도 부수지 않고 방문한 경우를 구분해서 기록하기 위해서 3차원 배열로 사용한다.
자료구조 선택
BFS로 구현하기 위해서 먼저 노드 구조체를 다음과 같이 정의한다. 각 노드는 위치값 정수 x,y를 가지고 있으며 최단 거리를 계산하기 위한 int변수 depth를 가지고 있다. 그리고 int 타입의 변수 key를 가지고 있다. 이 key는 벽을 한 번 부술 수 있는 기회가 있다면 1, 이미 벽을 한번 부수셔서 더 이상 벽을 부수지 못한다면 0의 값을 가진다.
struct Node {
Node(int _x, int _y, int key, int _depth)
: x(_x)
, y(_y)
, key(key) // 1: 벽을 부술 수 있는 노드, 0: 벽을 부술 수 없는 노드
, depth(_depth)
{}
int x;
int y;
int key;
int depth;
};그리고 문제를 풀기위한 클래스 Maze를 다음과 같이 정의했다. 먼저 벽과 길 등 지형을 표시할 map을 이차원 배열로 선언했다. 그리고 방문 기록 visited를 3차원 bool 타입 배열로 선언했다. 그래서 각 (x, y) 위치에서 벽을 부수고 온 노드일 경우 visited[x][y][0] 벽을 부수지 않고 온 노드일 경우 visited[x][y][1]에 방문 기록을 저장한다. 배열의 최댓값은 1,002로 지정했다. 이는 BFS알고리즘을 최적화하기 위함인데 그 이유는 다음과 같다. 보통 BFS에서 큰 계산량을 차지하는 부분이 바로 인접 노드의 인덱스 검사 부분이다. 예를 들어서 (0,0) 노드에서 시작할 경우 (0,0)의 인접 노드로 (-1,0)이 들어오지 않도록 우리는 항상 예외처리를 해야 하고 모든 노드에서 해당 예외처리는 4번씩 진행되기 때문에 가장 많은 비용을 차지한다. 하지만 우리가 1 ~ 1,000번 인덱스를 활용하고, 0번 인덱스와 1,001 인덱스의 방문 기록을 true로 설정한다면 별도의 예외처리를 하지 않더라도 범위를 벗어난 -1번 인덱스 혹은 1,0002번 인덱스에 접근하는 경우가 없어진다. 이 부분은 밑에 나올 Maze::InputData() 멤버함수 구현에서 확인할 수 있다.
class Maze {
public:
Maze(int _N, int _M) : N(_N), M(_M)
{}
void InputData();
int Search();
private:
static const int MAX = 1'002;
array<array <int, MAX>, MAX> map{};
array<array<array<bool, 2>, MAX>, MAX> visited{};
int N, M;
array<int, 4> dx{ 1,-1,0,0 };
array<int, 4> dy{ 0,0,1,-1 };
};Maze 클래스는 아래와 같이 사용할 수 있다.
int main() {
int N, M;
cin >> N >> M;
Maze maze(N, M); // Maze 클래스 생성
maze.InputData(); // 데이터 입력
cout << maze.Search(); // 최단거리 탐색 및 결과 출력
return 0;
}구현
데이터 입력
Maze::Input 멤버함수에서는 지형에 대한 데이터 map과 전체 맵 외부 위치의 방문 기록을 true로 설정하여 인덱스 범위를 초과하지 않도록 설정한다.
void Maze::InputData()
{
for (int i = 1; i < N + 1; ++i)
{
string str;
cin >> str;
for (int j = 1; j < M + 1; ++j)
{
// 각 위치에 노드 생성, 벽(true) or 길(false) 로 초기화
map[i][j] = str[j - 1] - '0';
}
}
for (int i = 0; i < N + 2; i++)
{
visited[i][0][0] = true;
visited[i][0][1] = true;
visited[i][M + 1][0] = true;
visited[i][M + 1][1] = true;
}
for (int i = 0; i < M + 2; i++)
{
visited[0][i][0] = true;
visited[0][i][1] = true;
visited[N + 1][i][0] = true;
visited[N + 1][i][1] = true;
}
}BFS 탐색
Maze::Search 멤버 함수에서는 큐를 활용한 BFS 탐색을 시행한다.
int Maze::Search()
{
if (N == 1 && M == 1)
return 1;
queue<Node> q;
// (1,1) 에 key 1개를 가지고 시작.
q.emplace(1, 1, 1, 1);
visited[1][1][1] = true;
while (!q.empty())
{
Node cur = q.front();
q.pop();
// 인접노드 검사
for (int i = 0; i < 4; ++i)
{
Node next(cur.x + dx[i], cur.y + dy[i], cur.key, cur.depth + 1);
// 목표 도착
if (next.x == N && next.y == M)
{
int retVal = next.depth;
return retVal;
}
// 다음 위치가 벽이고 방문한적이 없다면
if (map[next.x][next.y] == 1 && visited[next.x][next.y][0] == false && next.key == 1)
{
visited[next.x][next.y][0] = true;
next.key--;
q.emplace(next.x, next.y, next.key, next.depth);
}
// 다음 위치가 벽이 아니고, 방문한 적이 없다면
else if (map[next.x][next.y] == 0 && visited[next.x][next.y][next.key] == false)
{
visited[next.x][next.y][next.key] = true;
q.emplace(next.x, next.y, next.key, next.depth);
}
}
}
// 탐색에 실패한 경우
return -1;
}각 노드는 현재 위치, 탐색 깊이와 더불어 key라는 정수 변수를 가진다. key가 1인 노드는 벽을 부술 기회가 남은 노드이고, key가 0인 노드는 더 이상 벽을 부술 수 없는 노드이다. 인접 노드를 방문했는데 만약 인접 노드가 벽이고, 그 벽의 방문 기록이 없으며, 벽을 부술 수 있다면 벽을 부수고 방문하게 된다. 때문에 visited[x][y][0]의 방문 기록을 true로 설정하고, next노드의 key값을 감소시킨 후 큐에 삽입한다.
반면, 다음 위치가 벽이 아니라면, key값의 변화 없이 방문 기록만 설정 후 큐에 삽입한다. 이때 방문 기록은 벽을 한번 부수고 온 경우와 벽을 한 번도 부수지 않고 온 경우를 따로 관리해야 한다. 그래서 if문을 살펴보면 visited[next.x][next.y][next.key]로 표현되어 있음을 확인할 수 있다.
성능
해당 알고리즘은 최악의 경우 모든 노드(\(N \cdot M\))를 한 번씩 방문해야 한다. 따라서 시간 복잡도는 \(O(N \cdot M)\)이다. 그리고 공간 복잡도 또한 모든 위치에 대한 방문 기록인 visited 배열과 map 2차원 배열을 가지며, 큐에 삽입되는 노드의 개수도 전체 전체 노드 수에 비례하여 커진다. 따라서 공간 복잡도는 \(O(N \cdot M)\) 이라 할 수 있다.
전체 소스 코드
#include <iostream>
#include <array>
#include <queue>
#include <string>
#define endl '\n'
using namespace std;
struct Node {
Node(int _x, int _y, int key, int _depth)
: x(_x)
, y(_y)
, key(key)
, depth(_depth)
{}
int x;
int y;
int key;
int depth;
};
class Maze {
public:
Maze(int _N, int _M) : N(_N), M(_M)
{}
void InputData();
int Search();
private:
static const int MAX = 1'002;
array<array <int, MAX>, MAX> map{};
array<array<array<bool, 2>, MAX>, MAX> visited{};
int N, M;
array<int, 4> dx{ 1,-1,0,0 };
array<int, 4> dy{ 0,0,1,-1 };
};
void Maze::InputData()
{
for (int i = 1; i < N + 1; ++i)
{
string str;
cin >> str;
for (int j = 1; j < M + 1; ++j)
{
// 각 위치에 노드 생성, 벽(true) or 길(false) 로 초기화
map[i][j] = str[j - 1] - '0';
}
}
for (int i = 0; i < N + 2; i++)
{
visited[i][0][0] = true;
visited[i][0][1] = true;
visited[i][M + 1][0] = true;
visited[i][M + 1][1] = true;
}
for (int i = 0; i < M + 2; i++)
{
visited[0][i][0] = true;
visited[0][i][1] = true;
visited[N + 1][i][0] = true;
visited[N + 1][i][1] = true;
}
}
int Maze::Search()
{
if (N == 1 && M == 1)
return 1;
queue<Node> q;
// (1,1) 에 key 1개를 가지고 시작.
q.emplace(1, 1, 1, 1);
visited[1][1][1] = true;
while (!q.empty())
{
Node cur = q.front();
q.pop();
// 인접노드 검사
for (int i = 0; i < 4; ++i)
{
Node next(cur.x + dx[i], cur.y + dy[i], cur.key, cur.depth + 1);
// 목표 도착
if (next.x == N && next.y == M)
{
int retVal = next.depth;
return retVal;
}
// 다음 위치가 벽이고 방문한적이 없다면
if (map[next.x][next.y] == 1 && visited[next.x][next.y][0] == false && next.key == 1)
{
visited[next.x][next.y][0] = true;
next.key--;
q.emplace(next.x, next.y, next.key, next.depth);
}
// 다음 위치가 벽이 아니고, 방문한 적이 없다면
else if (map[next.x][next.y] == 0 && visited[next.x][next.y][next.key] == false)
{
visited[next.x][next.y][next.key] = true;
q.emplace(next.x, next.y, next.key, next.depth);
}
}
}
// 탐색에 실패한 경우
return -1;
}
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 클래스 생성
maze.InputData(); // 데이터 입력
cout << maze.Search(); // 최단거리 탐색 및 결과 출력
return 0;
}