BOJ 2178 : 미로탐색

[코드 참조!!!!!!!]

blog.encrypted.gg/941?category=773649

 

[문제]

- N*M 크기의 미로가 주어지고 갈 수 있는 길이 0과 1로 표시된다. 가로,세로로 인접한 칸으로만 이동이 가능하다. 이 때, 미로의 (1,1)위치에서 (n,m)까지 최소 거리를 계산하여 출력하는 문제이다.

- 입력 : n, m (미로 크기 1<=n,m<=100) & 미로 정보가 띄어쓰기 없는 정수들의 집합

- 출력 : (1,1)부터 (n,m)까지 최소 거리

 

[풀이]

- BFS알고리즘을 활용해 최단 거리를 구한다.

- map[x][y]가 1인 경우에만 탐색을 하도록 한다.

- '거리'를 구할 때 dist배열을 활용해 저장한다. ***굳이 최소값을 찾으려 안해도 된다...

- 띄어쓰기 없이 정수가 입력될 때 cin으로 처리가 안되서 scanf를 활용했다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

#define X first
#define Y second

int map[101][101];
bool check[101][101];
int dist[101][101];
int n, m;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int main() {
	//미로의 크기 n,m 입력
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			//띄어쓰기 없이 입력받을 때 사용
			int temp;
			scanf("%1d", &temp);
			map[i][j] = temp;
		}
	}
	//bfs탐색에 사용할 queue선언
	queue<pair<int, int>>q;
	check[0][0] = 1; 
	dist[0][0] = 1;
	q.push({ 0,0 });

	while (!q.empty()) {
		pair<int, int>cur = q.front(); 
		q.pop();

		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			if (nx >= n && ny >= m)break;
			if (nx < 0 || nx >= n || ny < 0 || ny >= m)continue;
			if (check[nx][ny] || map[nx][ny] != 1)continue;
			check[nx][ny] = 1;
			q.push({ nx,ny });
			//거리를 계산해준다.
			dist[nx][ny] = dist[cur.X][cur.Y] + 1;
		}
	}
	//미로의 (n,m)위치의 dist값을 보면 저절로 최솟값 출력
	cout << dist[n - 1][m - 1] << "\n";

	return 0;
}