[백준 2178번/c++] 미로 탐색(DFS 시간초과와 BFS)

알고리즘

 

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

---

깊이 우선 탐색 DFS: 시간 초과

DFS를 이용하여 최단거리를 찾고자 하는 경우 완전 탐색 후 가장 작은 값을 선택하여야 하므로 경로가 많아질 수 있고 이렇게 되면 시간 복잡도가 커진다.

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int map[101][101], ch[101][101], n, m;
int dx[4]={1, 0, -1, 0};
int dy[4]={0, 1, 0, -1};
int cnt=1, minn=2147000000;
void DFS(int x, int y){
	int xx, yy, i;
	if(x==n && y == m){
		if(cnt<minn){
			minn=cnt;
		}
		return;
	} else{
		for(i=0; i<4; i++){
			xx=x+dx[i];
			yy=y+dy[i];
			if(xx<1||xx>n||yy<1||yy>m){
				continue;
			}
			if(map[xx][yy]==1 && ch[xx][yy]==0){
				ch[xx][yy]=1;
				cnt++;
				DFS(xx, yy);
				ch[xx][yy]=0;
				cnt--;
			}
		}
	}
}

int main(){
	int i, k;
	scanf("%d %d", &n, &m);
	for(i=1; i<=n; i++){
		for(k=1; k<=m; k++){
			scanf("%1d", &map[i][k]);
		}
	}
	ch[1][1]=1;
	DFS(1, 1);
	printf("%d\n", minn);
	
	return 0;
}

---

너비 우선 탐색 BFS: 성공

최단거리를 보장하는 BFS를 통해 구하여야 한다.

#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

int map[101][101], dis[101][101], n, m;
int dx[4]={1, 0, -1, 0};
int dy[4]={0, 1, 0, -1};
int cnt=1, minn=2147000000;
queue<pair<int, int> > q;

void BFS(int x, int y){
	q.push(make_pair(x, y));
	dis[x][y]=1;
	while(!q.empty()){
		x=q.front().first;
		y=q.front().second;
		q.pop();
		for(int i=0; i<4; i++){
			int nx=x+dx[i];
			int ny=y+dy[i];
			if(nx>0 && nx<=n && ny>0 && ny<=m 
			&& dis[nx][ny]==0 && map[nx][ny]==1){
				q.push(make_pair(nx, ny));
				dis[nx][ny]=dis[x][y]+1;
			}
		}
	}
}

int main(){
	// freopen("input.txt", "rt", stdin);
	int i, k;
	scanf("%d %d", &n, &m);
	for(i=1; i<=n; i++){
		for(k=1; k<=m; k++){
			scanf("%1d", &map[i][k]);
		}
	}
	BFS(1, 1);
	printf("%d\n", dis[n][m]);
	
	return 0;
}

 

---

아직 DFS BFS 문제를 많이 풀어보지 않아 많이 풀어보며 적응해야할 것 같다.