C++ / 2178 / 미로 탐색 ( 너비 우선 탐색 )

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

문제 요약

n * m 크기의 배열로 표현되는 미로가 있을때 1은 이동할 수 있는칸 0은 이동할 수 없는 칸 입니다.

( 1, 1 )에서 출발하여 ( n, m )의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성해야합니다.

문제 풀이

1. 숫자를 받을 2차원 배열과 방문했었는지 식별하기 위해 bool 2차원 배열을 만들고 4방향 으로 x축 y축 좌표를 탐색하기 위한 배열 2개를 만들어줍니다.

2. n 과 m을 입력 받고 2차원 벡터 배열 사이즈를 재정의 해줍니다.

3. 2차원 반복문으로 값을 string으로 받고 벡터에 문자를 숫자로 바꿔주어 넣습니다.

4. bfs 함수를 만들어줍니다. bfs는 너비 우선 탐색으로 루트 노드에서 시작해서 인접한 노드를 먼저 탐색 하는 방법입니다.

5. 함수 인자로 시작 지점( 루트 )를 받아줍니다.

6. 큐를 만들어 인자를 넣어줍니다.

7. 탐색 인덱스를 담을 변수를 만들고 큐의 ( 탐색의 기준이 될 노드 ) 를 넣어줍니다.

8. 큐를 pop() 하여 탐색한 노드를 큐에서 지워줍니다.

9. 4번 돌아가는 ( 4방향 탐색 ) 반복문을 선언하여 위에 만든 변수에 탐색 범위를 지정 ( 4방향 으로 탐색 하도록 )합니다.

10. 탐색할 노드가 갈수 있는 노드인지, 미로의 크기를 넘었는지 방문했었는지 검사합니다.

11. 해당 사항 없으면 방문 체크를 하고 지나온 노드에 가중치를 더해줍니다.( 갈 수 있는 횟 수 )

12. 이렇게 하면 원하는 노드에 몇번만에 갈 수 있는지 가중치가 쌓입니다.

13. 합수가 종료 되면 출력으로 [n-1][m-1] ( 목표 노드 ) 의 노드 값을 출력합니다.

주의할 점

이 문제는 bfs를 사용하여 풀어야 하는 문제입니다.

기본 적으로 bfs에 대한 이론이 있어야 풀 수 있기 때문에 먼저 알고리즘을 한번 보고 오는걸 추천합니다.

방문 했던 노드인지, 미로의 크기를 넘어가지 않는지 조건을 제대로 주는 것이 중요합니다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int dx[4] = { -1, 0 , 1, 0 };
int dy[4] = { 0, 1, 0, -1};

vector<vector<int>>v;
bool visit[100][100];
int n, m;
string s;

void bfs(int x, int y)
{
	// 첫 시작 방문 체크
	visit[x][y] = 1;
	queue<pair<int, int>> q;
	// 큐에 첫 방분 지점 넣음
	q.push(make_pair(x, y));

	while(!q.empty())
	{
		x = q.front().first;
		y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int xx = x + dx[i];
			int yy = y + dy[i];

			// 미로 크기 벗어나면 무시
			if (xx < 0 || xx >= n || yy < 0 || yy >= m)
			{
				continue;
			}
			// 이동 할 수 없으면 무시
			if (v[xx][yy] == 0)
			{
				continue;
			}

			// 방문한 곳인지 체크
			if (!visit[xx][yy])
			{
				visit[xx][yy] = 1;
				// 지나온 지점에 가중치 더하기
				v[xx][yy] = 1 + v[x][y];
				// 큐에 탐색 지점 쌓기
				q.push(make_pair(xx, yy));
			}
		}
	}
}


int main()
{
	cin >> n >> m;
	// 백터 사이즈를 n*m으로
	v.resize(n, vector<int>(m));

	for (int i = 0; i < n; i++)
	{
		cin >> s;
		for (int j = 0; j < m; j++)
		{
			v[i][j] = s[j] - '0';
		}
	}
	bfs(0, 0);
	cout << v[n - 1][m - 1];

	return 0;
}

반응형

예제1

4 6
101111
101010
101011
111011

결과1

예제2

4 6
110110
110110
111111
111101

결과2

예제3

2 25
1011101110111011101110111
1110111011101110111011101

결과3

예제4

7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111

결과4