맵 최단 거리 구하기

https://school.programmers.co.kr/learn/courses/30/lessons/1844

해당 문제를 푸는데, BFS로 접근하면 될거 같은데 BFS를 잘 모르겠어서 일단 생각이 나는 DFS로 풀어보았다.
틀렸다. 효율도 안좋고, 틀리기까지 했다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

vector<int> successVisitCounts;
void DFS(vector<vector<int>>& maps, vector<vector<bool>>& visits, const pair<int, int>& targetPos, pair<int, int> pos, int visitCount)
{
	visitCount++;
	visits[pos.first][pos.second] = true;

	if (pos == targetPos)
		successVisitCounts.push_back(visitCount);

	//방문 위치
	int yPos[] = { -1, +1, 0, 0 };
	int xPos[] = { 0, 0, -1, +1 };

	for (int i = 0; i < 4; i++)
	{
		pair<int, int> visitPos = pos;
		visitPos.first += yPos[i];
		visitPos.second += xPos[i];

		if (visitPos.first >= 0 && visitPos.first < maps.size() &&
			visitPos.second >= 0 && visitPos.second < maps[0].size() &&
			maps[visitPos.first][visitPos.second] && visits[visitPos.first][visitPos.second] == false)
			DFS(maps, visits, targetPos, visitPos, visitCount);
	}

	visits[pos.first][pos.second] = false;
	visitCount--;
}

int solution(vector<vector<int>> maps)
{
	pair<int, int> startPos = make_pair(0, 0);
	pair<int, int> targetPos = make_pair(maps.size() - 1, maps.size() - 1);

	vector<vector<bool>> visits(maps.size());
	for (vector<bool>& vec : visits)
		vec.resize(maps[0].size());

	int visitCount = 0;
	DFS(maps, visits, targetPos, startPos, visitCount);

	auto minIter = min_element(successVisitCounts.begin(), successVisitCounts.end());

	return minIter == successVisitCounts.end() ? -1 : *minIter;
}

int main()
{
	cout << solution({ {1, 0, 1, 1, 1}, {1, 0, 1, 0, 1}, {1, 0, 1, 1, 1}, {1, 1, 1, 0, 1}, {0, 0, 0, 0, 1} }) << endl;
}

예시는 성공해서 될 줄 알았는데 안됬다.
역시 최단거리이므로 BFS로 푸는게 맞는 것 같다.

---

단어 변환

https://school.programmers.co.kr/learn/courses/30/lessons/43163

최단 횟수라 BFS 맞는거 같긴한데..
사람이 하루 아침에 익숙해 질 수는 없으므로 알고있는 DFS로 풀었다.
이번엔 통과도 되서 정답이긴하다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> endCounts;
void DFS(vector<string>& words, vector<bool>& visit, const string& target, string str, int count)
{
	if (str == target)
	{
		endCounts.push_back(count);
		return;
	}

	for (int i = 0; i < words.size(); i++)
	{
		const string& nowStr = words[i];
		int diff = 0;

		if (nowStr == str || visit[i])
			continue;

		//차이점이 1인지 검사
		for (int j = 0; j < str.size(); j++)
			if (str[j] != nowStr[j])
				diff++;

		if (diff == 1)
		{
			visit[i] = true;
			DFS(words, visit, target, nowStr, count + 1);
			visit[i] = false;
		}
	}
}

int solution(string begin, string target, vector<string> words)
{
	auto targetIter = find(words.begin(), words.end(), target);
	if (targetIter == words.end())
		return 0;

	vector<bool> visit(words.size());
	DFS(words, visit, target, begin, 0);

	auto minIter = min_element(endCounts.begin(), endCounts.end());
	return endCounts.size() ? *minIter : 0;
}

int main()
{
	cout << solution("hit", "cog", { "hot", "dot", "dog", "lot", "log", "cog" }) << endl;
}