BOJ_2178_미로탐색

이 글은 개발공부를 하고 있는 "학생"의 글입니다. 참고하시되, 오류가 있음을 항상 유의해주시길 바랍니다. 혹시 오류를 발견하신 분은 댓글 남겨주시면 정말 감사드리겠습니다:)

이번에도, BFS를 풀어보겠습니다. BFS는 워낙 자주 나오는 문제 유형이고, 조금씩 변형되서 나오다 보니, 변형 예제들을 많이 익히면서 변경 사항을 적용하는 것이 중요하다 생각이 듭니다.

문제 출처 : https://www.acmicpc.net/problem/2178

접근 방법

• 문제 시작부터 N*M 배열이 나온다.
  -> grid 문제임을 확인할 수 있다.(BFS? DFS?)
• 문제에서 구하고자 하는 것은 (1, 1)에서 시작하여 (N, M)위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 것이다.
• N, M(2 ~ 100)으로, O(N^2)까지는 괜찮을 것 같다.
• DFS도 익히기 위해서, DFS, BFS 두 풀이를 모두 도전해볼까 한다.

BFS 풀이

#include<iostream>
#include<queue>
using namespace std;

int n, m;
int arr[102][102];
int vis[102][102];
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
string S;

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> S;
		for (int j = 0; j < m; j++) {
			if (S[j] == '1')arr[i][j] = 1;
			else if (S[j] == '0')arr[i][j] = 0;
		}
	}
	// BFS수행
	queue<pair<int, int>> q;
	q.push({ 0, 0 });
	vis[0][0] = 1;
	while (!q.empty()) {
		auto curr = q.front(); q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = curr.first + dx[i];
			int ny = curr.second + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (vis[nx][ny] != 0 || arr[nx][ny] == 0) continue;
			q.push({ nx, ny });
			vis[nx][ny] = vis[curr.first][curr.second] + 1;
		}
	}
	cout << vis[n - 1][m - 1];
	return 0;
}

DFS 풀이 -> 공부하고 풀어볼 예정이다.