알고리즘 :: 백준 :: 2178 - 미로탐색

 

 

 

❔문제

🔗문제링크

 

🔄 문제 및 입출력 조건 파악

입력:

• N × M 미로, '붙어서' 들어오는 입력
  
  • `scanf("%c")` 이용
  • 또는 `std::string`으로 한 줄 입력받은 후 `for()`로 처리
  • 또는 `std::string`으로 한 줄 입력받은 후 그대로 사용하기
• 2 ≤ N, M ≤ 100

출력: 

• (N, M)에 도달하기 까지 밟아야 하는 최소 칸 수
• 시작하는 칸, 도착하는 칸도 밟은 칸 수에 포함됩니다.

✏️ 문제풀이

최소 칸 수 = 최적해

• 가중치 없음 (모든 칸이 한 칸 이동에 동일하게 한 칸 소요) = BFS 이용
• 방문표시 후 시작점 queue에 `push`
• 4방향 중 갈 수 있는 칸은 queue에 `push`하고 방문표시 합니다.
• queue가 빌 때까지 반복합니다.

4방향 검사하기

• 미로의 경계범위를 넘어서지 않았고,
• 이동할 수 있는 칸이고,
• 이미 방문한 칸도 아니라면, 진행 가능합니다.

4방향을 나타내는 코드는 다음과 같습니다.

constexpr int dy[] = {-1, 0, 1, 0};
constexpr int dx[] = {0, 1, 0, -1};

 

또는

constexpr int d[][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

 

본인에게 편한 방식으로 사용하면 됩니다.

📝 코드

#include <bits/stdc++.h>
using namespace std;

constexpr int dy[] = {-1, 0, 1, 0};
constexpr int dx[] = {0, 1, 0, -1};

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	
	int N, M;
	cin >> N >> M;
	
	vector<string> arr(N);
	for (int i = 0; i < N; ++i) cin >> arr[i];
	
	vector<vector<int>> visited(N, vector<int>(M, 0));
	
	queue<pair<int, int>> q;
	q.push({0, 0});
	visited[0][0] = 1;
	while (!q.empty()) {
		int cy, cx; tie(cy, cx) = q.front();
		q.pop();
		for (int i = 0; i < 4; ++i) {
			int ny = cy + dy[i], nx = cx + dx[i];
			if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
			if (arr[ny][nx] == '0' || visited[ny][nx]) continue;
			q.push({ny, nx});
			visited[ny][nx] = visited[cy][cx] + 1;
		}
	}
	cout << visited[N - 1][M - 1] << '\n';
}

 

🔗 코드 링크

🕧 결과