[Baekjoon] 2178번 미로 탐색(C++)

www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

Level: Level 1

풀이: 기존 코드 참고

Language: C++

프로그램: Visual Studio 2017

 

 

 

문제설명

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

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

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

 

입력/출력

입력

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

입력 예

4 6 101111 101010 101011 111011

출력

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

출력 예

15

 

풀이

 

http://blog.naver.com/PostView.nhn?blogId=and_lamyland&logNo=221381111402&parentCategoryNo=&categoryNo=31&viewDate=&isShowPopularPosts=true&from=search

[백준 문제 32] C++ 2178 미로 탐색. (BFS)

• 중간에 어려움을 느껴 다른 사람의 풀이를 보고 문제를 해결하였다.

• BFS 알고리즘, 너비 우선 탐색 알고리즘을 이용하여 문제를 해결하였다.

• (0, 0)에서 출발하여 (N-1, M-1)에 도착하도록 하였고 방문이 가능한 곳을 도착하면 이동 전에 있던 곳에 현재 위치까지 최소한의 칸 수로 값을 바꿔주었다.

 

 

Code

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<queue>

using namespace std;

int N, M; //배열의 크기 입력받기
int arr[101][101]; //지나온 길 기록하기
int dir[4][2] = { {0,-1}, {1,0}, {0, 1}, {-1, 0}};
queue<pair<int, int> > q;   //큐 생성

// 출발점 (0,0) 에서 시작해 (N-1, M-1) 까지 BFS 탐색을 하면서 이동할 때 값에 1을 더해준다.
// bfs 알고리즘을 이용한다.
void bfs() {
	q.push(make_pair(0,0));
	pair<int, int> current;
	int next_x;
	int next_y;
	while (!q.empty()) {
		// 현재 배열 위치가 current에 들어간다.
		current = q.front();
		q.pop();

		//up, down, left, right 검사하기
		for (int i = 0; i < 4; i++) {
			next_x = current.second + dir[i][0];
			next_y = current.first + dir[i][1];

			if (0 <= next_x && next_x < M && 0 <= next_y && next_y < N && arr[next_y][next_x] == 1) {
				q.push(make_pair(next_y, next_x)); //방문한 곳 push
				arr[next_y][next_x] = arr[current.first][current.second] + 1;
			}
		}
	}
	return;
}
int main(void) {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			//미로를 0 또는 1로 입력을 받는다.
			//cin >> arr[i][j];
			scanf("%1d", &arr[i][j]); //하나씩 입력 받기
		}
	}
	bfs();
	cout << arr[N - 1][M - 1];
	return 0;
}

 

ScreenShot