[C/C++ 백준 2178번] 미로 탐색 (Silver 1)

www.acmicpc.net/problem/2178

2178번: 미로 탐색

DFS로 해결하려 했다가 실패,, 가장 짧은 경로 하나만 찾으면 되는 것이므로, bfs로 푸는 것이 훨씬 합당하다.

해당 내용만 알면 배열과 벡터, 큐를 이용해서 그래프를 만들어 준 뒤 풀면 된다.

 

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
int N, M, array[102][102];
bool visit[102][102];
typedef struct point{
	int x;
	int y;
	int depth = 0;
}point;
vector <point> graph[102][102];
int xmove[4] = {-1, 1, 0, 0};
int ymove[4] = {0, 0, 1, -1};
void bfs(){
	queue <point> q;
	point a; a.x=1; a.y=1;
	q.push(a); visit[1][1] = true;
	while(!q.empty()){
		point tmp = q.front();
		q.pop();
		if(tmp.x == N && tmp.y == M){
			printf("%d", 1+tmp.depth);
			break;
		}
		for(int i=0; i<graph[tmp.x][tmp.y].size(); i++){
			for(int j=0; j<4; j++){
				if(visit[tmp.x+xmove[j]][tmp.y+ymove[j]] == false
				&& array[tmp.x+xmove[j]][tmp.y+ymove[j]] == 1){
					visit[tmp.x+xmove[j]][tmp.y+ymove[j]] = true;
					point a;
					a.x = tmp.x+xmove[j];
					a.y = tmp.y+ymove[j];
					a.depth = tmp.depth+1;
					q.push(a);				
				}
			}	
		}
	}
}
int main(void){
	scanf("%d %d", &N, &M);
	memset(array, 0, 102*102*sizeof(int));
	for(int i=0; i<=N+1; i++){
		for(int j=0; j<=M+1; j++){
			visit[i][j] = false;
			array[i][j] = 0;
		}
	}
	for(int i=1; i<=N; i++){
		for(int j=1; j<=M; j++){
			scanf("%1d", &array[i][j]);
			if(array[i][j]==1 && array[i][j-1]==1){
				point a; a.x=i; a.y=j;
				point b; b.x=i; b.y=j-1;
				graph[i][j].push_back(b);
				graph[i][j-1].push_back(a);
			}
			if(array[i][j]==1 && array[i-1][j]==1){
				point a; a.x=i; a.y=j;
				point b; b.x=i-1; b.y=j;
				graph[i][j].push_back(b);
				graph[i-1][j].push_back(a);
			}
		}
	}
	bfs();
}