[백준(BOJ)] 2178번 : 미로 탐색 - C++[CPP]

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

2178번: 미로 탐색

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

 

---

 

⊙ 문제 접근 과정

 

너비 우선 탐색인 BFS를 이용하여 문제를 접근했다. dx와 dy의 int 배열을 만들어 상하좌우로 움직일 수 있게 하였고 범위를 벗어나지 않으면 계속하여 탐색하도록 설계했다.

 

pair <int, int>를 사용하였는데 first, second인 두 변수를 저장할 수 있는 struct이다.

이차원 배열의 미로에서 사용하기 위한 용도로 사용했다.

 

최대한 이해하기 쉽고 보기 좋게 코드를 짜보았다.

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <queue>
using namespace std;
 
string map[100];
int dis[100][100];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int n,m;
queue<pair<int, int> > q;

void bfs(int x,int y) {
    q.push(make_pair(x, y));
	dis[x][y] = 1;
	while (!q.empty()) {
		x = q.front().first;
		y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < m
			&& dis[nx][ny] == 0 && map[nx][ny] == '1') {
				q.push(make_pair(nx, ny));
				dis[nx][ny] = dis[x][y] + 1;
			}
		}
	}
}
int main(void) {
    cin >> n>> m;
    for (int i = 0; i < n; i++)
		cin >> map[i];
    bfs(0,0);
	cout << dis[n - 1][m - 1]; 
}

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!