2178 미로찾기

미로 탐색

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

192 MB

47353

15982

10059

32.993%

문제

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

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

struct Pair{
	int x;
	int y;
};


int bfs();

bool maze[101][101];
int visited[101][101];
int n,m;
queue<Pair> que;

int main(){

	freopen("input.txt","r",stdin);

	ios::sync_with_stdio(false);
	cin.tie(0);

	memset(maze, false, sizeof(maze));
	memset(visited, 0, sizeof(visited));

	cin >> n >> m;

	string temp;
	for(int i=0; i<n; ++i){
		cin>>temp;
		for(int j=0; j<m; ++j){
			if( temp.at(j) == '1' ){
				maze[i][j] = true;
			} 
		}
	}
// for(int i=0; i<n; ++i){
// 		for(int j=0; j<m; ++j){
			
// 			cout<<maze[i][j]<<" ";
// 		}
// 		cout<<"\n";
// 	}
	while(!que.empty()){ que.pop(); }
	que.push({0,0});
	visited[0][0]++;
	cout<<bfs();
	// for(int i=0; i<n; ++i){
	// 	for(int j=0; j<m; ++j){
			
	// 		cout<<visited[i][j]<<" ";
	// 	}
	// 	cout<<"\n";
	// }


	return 0;
}



int bfs(){

	Pair p;
	
	while( !que.empty() ){

		p = que.front();
		que.pop();
		
		if( p.x==n-1 && p.y==m-1 ){break;}

		if( p.x+1 < n && visited[p.x+1][p.y]==0 && maze[p.x+1][p.y] ){ //check bottom
			que.push({p.x+1, p.y});
			visited[p.x+1][p.y]= visited[p.x][p.y]+1;

		}
		if( p.x-1 >= 0 && visited[p.x-1][p.y]==0 && maze[p.x-1][p.y]  ){ //check top
			que.push({p.x-1, p.y}); 
			visited[p.x-1][p.y]= visited[p.x][p.y]+1;

		}
		if( p.y+1 < m && visited[p.x][p.y+1]==0 && maze[p.x][p.y+1] ){ //check right
			que.push({p.x, p.y+1}); 
			visited[p.x][p.y+1]= visited[p.x][p.y]+1;

		}
		if( p.y-1 >= 0 && visited[p.x][p.y-1]==0 && maze[p.x][p.y-1]  ){ //check left
			que.push({p.x, p.y-1});
			visited[p.x][p.y-1]= visited[p.x][p.y]+1;

		}

		

	}

	return visited[n-1][m-1];

}

 

 

BFS로 서치하는 것 까지는 기억해 냈는데, 최단거리를 찾는것이 도저히 기억이 안나서 결국엔 찾아보았다.

 

아이디어1. 

visited를 방문or미방문으로 처리하지 않고, visited를 전 단계에서 서치될때마다 +1을 해주는 dp같은 방법을 깨달아서 지금 코드에 써먹었고,

 

아이디어2.

head,tail인덱스로 나누어서 각 단계 만큼 for문돌리고 카운트 1씩 증가하는 방법이 있었다.

당연히 아이디어 2가 메모리를 적게 먹을 것이다.

다음엔 아이디어2로 구현해 봐야지!

 

밑은 아이디어2로 구현한 분의 소스코드!

 

#include <stdio.h>
#include <vector>

typedef struct _point {
	int y, x;
} Point;

int main()
{
	int N, M, step, i, j, sz, y, x, head, tail;
	bool map[101][101];
	Point p, queue[10000];

	scanf("%d %d", &N, &M);
	for (i = 1; i <= N; i++)
		for (j = 1; j <= M; j++) {
			scanf("%1d", &map[i][j]);
			if (map[i][j])
				map[i][j] = 0;
			else
				map[i][j] = 1;
		}

	head = tail = 0;
	step = 1;
	map[1][1] = 1;
	queue[tail++] = { 1, 1 };

	while (head != tail) {
		sz = tail - head;
		for (i = 0; i < sz; i++) {
			p = queue[head++];
			y = p.y, x = p.x;
			if (y == N && x == M)
				goto EXIT;

			if (y - 1 > 0 && !map[y - 1][x]) {
				map[y - 1][x] = 1;
				queue[tail++] = { y - 1, x };
			}
			if (y + 1 <= N && !map[y + 1][x]) {
				map[y + 1][x] = 1;
				queue[tail++] = { y + 1, x };
			}
			if (x - 1 > 0 && !map[y][x - 1]) {
				map[y][x - 1] = 1;
				queue[tail++] = { y, x - 1 };
			}
			if (x + 1 <= M && !map[y][x + 1]) {
				map[y][x + 1] = 1;
				queue[tail++] = { y, x + 1 };
			}
		}

		step++;

	}

EXIT:
	printf("%d", step);

	return 0;
}