문제

DFS로 풀었으나 시간 초과가 나서 BFS로 다시 제출하니 통과되었다.

구글에 BFS DFS 차이를 검색해 읽어보자.

어떤 경우에 무엇을 사용하는 것이 좋은지 간단히 요약하자면

  • BFS
    • 현재 노드에서 가까운 곳부터 찾기 때문에 최단거리를 구할 때 유리
    • 답이 되는 경로가 여러 개인 경우에도 최단 경로 보장
  • DFS
    • 이동 과정에 제약이 있을 때 (예: 가중치가 있거나 경로에 같은 숫자가 있으면 안 된다는 등)
    • 이동한 정점의 값을 가지고 계속 연산을 하는 경우
    • 현 경로 상의 노드를 기억하기 때문에 적은 메모리 사용
    • 최단 경로 보장 X
    • 백트래킹 등에서 사용
#include <iostream>
#include <vector>
#include <queue> // bfs
#include <utility> // pair
#define MAX 101
using namespace std;

int m, n; // m:row n:col

bool map[MAX][MAX];
bool visited[MAX][MAX];
int dist[MAX][MAX];

int dr[4] = { -1, 1, 0, 0 }; // UP DOWN LEFT RIGHT
int dc[4] = { 0, 0, -1, 1 }; // UP DOWN LEFT RIGHT

void dfs(int r, int c) { // start from (r, c)
	queue< pair<int, int> > st;
	int nowR, nowC, nextR, nextC;
	int i;

	nowR = r; nowC = c;
	dist[nowR][nowC] = 1;
	st.push(make_pair(nowR, nowC));

	while (!st.empty()) {
		nowR = st.front().first;
		nowC = st.front().second;
		st.pop();

		if (map[nowR][nowC] && !visited[nowR][nowC]) {
			visited[nowR][nowC] = true;

			for (i = 0; i < 4; i++) {
				nextR = nowR + dr[i];
				nextC = nowC + dc[i];

				if (map[nextR][nextC] && !visited[nextR][nextC] && 0 <= nextR && nextR < m && 0 <= nextC && nextC < n) {
					dist[nextR][nextC] = dist[nowR][nowC] + 1;
					st.push(make_pair(nextR, nextC));

				}
			}
		}
	}
}

int solution(vector<vector<int> > maps) {
	int i, j;
	m = maps.size();
	n = maps[0].size();

	for (i = 0; i < m; i++) {
		for (j = 0; j < n; j++) {
			if (maps[i][j]) map[i][j] = true;
		}
	}

	dfs(0, 0);

	if (!dist[m - 1][n - 1]) return -1;
	else return dist[m - 1][n - 1];
}