[C++] 백준 2178번 미로 탐색

 

1) 문제설명

백준 Online Judge 2178번 미로 탐색

백준 Online Judge 2178번 미로 탐색

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

2) 아이디어

거리의 최소를 찾기 위해 BFS를 사용했다.

처음 좌표를 (1,1)로 설정하고 BFS를 통해 값이 1인 곳을 찾아 탐색하였다.

BFS로 탐색하기 때문에 1이 존재하는 모든 구간을 탐색한다.

따라서 전역 변수를 설정하여 1인 곳을 방문할 때마다 카운트를 세어주는 것이 아닌 거리에 따른 변수를 하나 설정하여 카운트를 센다.

또한 방문한 곳을 표시하거나 초기화시켜주지 않으면 큐의 메모리 초과가 일어나므로 방문한 곳을 표시하거나 초기화시켜주어야 한다.

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;
int arr[100][100];
int range[100][100]; // 거리저장
int n, m;

void bfs(int x, int y) {
	
	queue <pair<int,int>> q;
	q.push(make_pair(x,y));
	
	int dx[] = { 1,0,-1,0 }; // x좌표 움직임
	int dy[] = { 0,1,0,-1 }; // y좌표 움직임
	while (!q.empty()) {
		
		int x = q.front().first;
		int y = q.front().second;
		arr[x][y] = 0; // 방문한 곳 초기화
		
		q.pop();
		if (x == n && y == m) { // 목적지 도착하면 종료
			break;
		}
		for (int i = 0; i < 4; i++) { // 현재 위치에서 상하좌우에 1이있나 탐색
			int nx, ny; // 다음에 갈 좌표변수
			nx = x + dx[i]; 
			ny = y + dy[i];

			if (nx<1 || nx>n || ny<1 || ny>m) { // 범위를 넘어갈때
				continue;
			}
			if (arr[nx][ny] == 1) { // 현재 x,y 의 위치에서 상하좌우에 1이 있을경우
				range[nx][ny] = range[x][y] + 1; // 한칸씩 갈때마다 거리 + 1
				arr[nx][ny] = 0; // 내가 다음에 방문할 곳을 미리 초기화시켜서 메모리 초과를 막는다.
				q.push(make_pair(nx, ny)); // 큐에 넣는다
			}
		}
	}
}

int main() {

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%1d", &arr[i][j]);
		}
	}
	bfs(1, 1);
	cout << range[n][m] + 1;
}

queue의 pair선언과 make_pair를 잘 기억해두어야겠다.