https://www.acmicpc.net/problem/2178
2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net
이문제의 경우 일부러 DFS 로 풀어보았더니 시간초과가 나왔다. 이문제의 경우 목표지점까지 무조건 도착한다고 가정했기 때문에 DFS 보다 최소해를 구해주는 BFS로 푸는게 효율적이다.
DFS의 장점은 목표가 어디있는지 모를 때 도착지점에 도착하여 끝이난다고 생각되면 된다 나의 경우 깊이 우선탐색으로 도착할 수 있는 모든 경우의 수에 최솟값을 구하려다 보니 되추적 (백트래킹)방식을 사용하여 최소해를 구하려 했다
이렇게 푸니 문제가 시간초과가 발생하였다 혹시 모르니 이문제의 DFS (백트래킹) 버전도 첨부하도록 하겠다
BFS버전
#include <iostream>
#include <utility>
#include <queue>
using namespace std;
char maze[101][101] = { '0', };
int visited[101][101] = { 0, };//각 정점의 단계수를 표시하기 위함
int N = 0, M = 0;
queue<pair<int, int>>visitedqueue;
int main() {
int startx = 0, starty = 0;
cin >> N >> M;
for (int i = 0; i < N; i++) {
cin >> maze[i];
}
//시작점 삽입
startx = 0;
starty = 0;
visited[0][0] = 1;
visitedqueue.push({ startx, starty });
while (!visitedqueue.empty()) {
startx = visitedqueue.front().first;
starty = visitedqueue.front().second;
visitedqueue.pop();
if (maze[startx][starty + 1] == '1' && visited[startx][starty + 1] == false) {
visitedqueue.push({ startx,starty + 1 });
visited[startx][starty + 1] = 1 + visited[startx][starty];
}
if (maze[startx + 1][starty] == '1' && visited[startx + 1][starty] == false) {
visitedqueue.push({ startx+1,starty });
visited[startx+1][starty] = 1 + visited[startx][starty];
}
if (maze[startx - 1][starty] == '1' && visited[startx - 1][starty] == false) {
visitedqueue.push({ startx-1,starty });
visited[startx-1][starty] = 1 + visited[startx][starty];
}
if (maze[startx][starty - 1] == '1' && visited[startx][starty - 1] == false) {
visitedqueue.push({ startx,starty-1 });
visited[startx][starty - 1] = 1 +visited[startx][starty];
}
}
cout << visited[N - 1][M - 1];
}
극단적으로 첫번째 표가 이번문제에 삽입된다고 하면 위에코드의
visted배열은 이런식으로 자기자신의 단계를 나타내면서 확장 될것이다 3단계와 인접한 자식들은 모두 4단계로 마킹되면서 계속 단계를 확장 해 나갈것이다 이에 마지막에 몇단계에서 도착점이 나왔는지만 출력해주면 답이나온다
일단 극단적으로 이번 문제의 표를 나타내어 보면 어린식으로 자신의 자식들을 확장해나갈것이다
if (maze[startx][starty + 1] == '1' && visited[startx][starty + 1] == false) {
visitedqueue.push({ startx,starty + 1 });
visited[startx][starty + 1] = 1 + visited[startx][starty];
}
if (maze[startx + 1][starty] == '1' && visited[startx + 1][starty] == false) {
visitedqueue.push({ startx+1,starty });
visited[startx+1][starty] = 1 + visited[startx][starty];
}
if (maze[startx - 1][starty] == '1' && visited[startx - 1][starty] == false) {
visitedqueue.push({ startx-1,starty });
visited[startx-1][starty] = 1 + visited[startx][starty];
}
if (maze[startx][starty - 1] == '1' && visited[startx][starty - 1] == false) {
visitedqueue.push({ startx,starty-1 });
visited[startx][starty - 1] = 1 +visited[startx][starty];
}이 코드가 자기자신과 인접한 4방향중 아직 방문하지 않은 곳으로 가서 자기 자식임을 표시한다 표시방법은 나의 단계에서 1을 더해주는 방식으로 작성 하였다 또한 나의 자식들도 큐의 삽입함으로서 계속해서 자손들을 확인한다.
즉 극단적인 위의 표로 봤을때 큐의 값은 (0,0)->(0,1)(1,1)(1,0)->(0,2)(2,1)(2,2)(1,2)(0,0)->..... 이런식으로 큐의 값이 변화하게 된다. 그후 맨마지막에 도착지점이 몇번째인지 마크되어있을테니 이것을 그대로 출력해주면 된다.
DFS
DFS방식으로는 이문제를 풀 수 없다 백트래킹을 사용하지 않고서는 DFS는 도착지점에 도착하는 순간 끝나기 때문에 백트래킹을 사용하여 이전지점으로가 다른 루트를 찾아가는 방법을 사용하지만 이문제에서는 시간초과를 발생시킨다. 이에
DFS방식으로 푸는것을 추천하지 않는다
#include <iostream>
#include <utility>
#include <stack>
using namespace std;
char maze[101][101] = { '0',};
bool visited[100][100] = { false, };
int N = 0, M = 0;
int minnum = 10001;
stack<pair<int, int>> visitedvertex;
void dfs(int startx, int starty) {
visited[startx][starty] = true;
visitedvertex.push({ startx,starty });
if (startx == N-1 && starty == M - 1) {
if (visitedvertex.size() < minnum) {
minnum = visitedvertex.size();
}
}
else{
if (maze[startx][starty + 1] == '1' && visited[startx][starty + 1] == false) {
starty += 1;
dfs(startx, starty);
starty -= 1;
}
if (maze[startx + 1][starty] == '1' && visited[startx + 1][starty] == false) {
startx += 1;
dfs(startx, starty);
startx -= 1;
}
if (maze[startx - 1][starty] == '1' && visited[startx - 1][starty] == false) {
startx -= 1;
dfs(startx, starty);
startx += 1;
}
if (maze[startx][starty - 1] == '1' && visited[startx][starty - 1] == false) {
starty -= 1;
dfs(startx, starty);
starty += 1;
}
}
visited[startx][starty] = false;
visitedvertex.pop();
}
int main() {
int startx = 0, starty = 0;
cin >> N >> M;
for (int i = 0; i < N; i ++) {
cin >> maze[i];
}
dfs(0, 0);
cout << minnum;DFS방식은 재귀를 사용하여야 한다 이에 재귀를 사용하면서 스택을 섞어서 사용하였다 자신이 방문할때 스택에다가 값을 쌓아올린다. 이후 도착점에 도착했을 때 도착한 최솟값과 비교하여 작은값을 저장하여 DFS로 갈 수 있는 방법중 최솟값을 출력하는게 내가 한방법이다 DFS는 일단 불러지는 순간 자기자신을 스택에 쌓는다 그후 자신의 4방향을 탐색하여 방문한적이 없으면 쌓는다 하지만 방문할곳이 없으면 다시 스택에서 나온다 이것을 반복하여 방문한곳을 방문하지 않고 끝점 까지 도달하는 경우의 수들중 최소의 점만을 거쳐서 도착하는 값을 출력한다
7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111이경우의 visitedvertex의 값은
0,0
0,1
1,1
.
.
.
..
6,6
순으로 쌓이고 끝점에 도달했으니 minnum값을 비교후 갱신하고
다시 자기이전으로 계속돌아가 분기가 발생한지점까지 다시 돌아간다 그러므로
0,0
0,1 까지돌아간 후
0,2
0,3
.
.
.
...
6,6 까지 간다 그후 minnum값과 비교하여 이제 모든 길을 가보았다면
minnum값을 출력후 끝나게 된다