Algorithm

BOJ 2178 - 미로 탐색

알고리즘/DFS∕BFS

문제




간단한 BFS를 이용한 길 찾기 문제이다. 알고리즘 분류는 BFS로 되어있는데 당연히 DFS로도 된다. 나는 BFS로 구현했다.


소스


#include <iostream>
#include <queue>
using namespace std;

struct pt{
	int x;
	int y;
};

int map[501][101] = {0};
int visit[501][101] = {0};
queue<pt> q;

void setVisit(int x, int y, pt o){
	pt next;
	next.x = x;
	next.y = y;
	q.push(next);
	visit[y][x]+=visit[o.y][o.x]+1;
}
int main(){
	
	int n,m,i,j;char c;
	pt o;
	cin>>n>>m;
	for(i=0;i<n;i++){
		for(j=0;j<m;j++) {
			cin >> c;
			map[i][j]=c-'0';
		}
	}
	o.x=0;o.y=0;
	q.push(o);
	visit[0][0]=1;
	while(!q.empty()){
		pt front = q.front();
		q.pop();
		if(front.x-1 >= 0 && !visit[front.y][front.x-1] && map[front.y][front.x-1])
			setVisit(front.x-1,front.y,front);
		if(front.x+1 < m && !visit[front.y][front.x+1] && map[front.y][front.x+1])
			setVisit(front.x+1,front.y,front);
		if(front.y-1 >= 0 && !visit[front.y-1][front.x] && map[front.y-1][front.x])
			setVisit(front.x,front.y-1,front);
		if(front.y+1 < n && !visit[front.y+1][front.x] && map[front.y+1][front.x])
			setVisit(front.x,front.y+1,front);
	}
	cout << visit[n-1][m-1] << '\n';
}


각 줄마다 띄어쓰기 없이 미로가 주어지므로 char 형으로 받은 다음 '0'(48)을 빼주어 정수형으로 바꾸어주었다.


큐에는 이번에 탐색해야할 좌표 값을 저장해야하므로 x,y값을 가지는 구조체를 만들어 좌표값을 저장시켜 주었고 맨 처음 시작할때 0,0 좌표 변수를 만들어 큐에 넣어주고 시작하게 했다.


탐색을 할때 상하좌우에 이동 할 수 있으며 방문하지 않은곳이 있다면 방문을 했다는 표시를 하고(어차피 큐에 넣고 나중에 방문할것이니 미리 표시해도 상관이 없다) visit[y][x]변수에 몇 번 이도해서 x,y 좌표에 왔는지에 대한 횟수를 적어두게하였다.