[Programmers]#Level2_방문 길이, 미로 찾기 유형, BFS, 너비 우선 탐색

 

#1. 문제

프로그래머스

 

---

 

#2. 풀이

 

1. BFS

[자료구조]#6_그래프

너비 우선 탐색은 그래프의 모든 정점을 탐색하는 방법 중 하나입니다. BFS는 현재 정점과 인접한 정점들을 우선적으로 탐색합니다. 일반적으로, BFS는 큐 자료구조를 활용하여 구현합니다. 

 

2. 미로 찾기 유형, 이동 값이 동일하면 BFS!

1. 먼저, 현재 정점으로부터 인접한 정점들을 찾기 위해 'U', 'D', 'R', 그리고 'L'을 키로 설정하고 각각 현재 정점으로부터 X좌표와 Y좌표의 이동 값을 값으로 map을 초기화합니다.
2. 동일한 가중치의 미로 찾기 유형에서 활용하는 BFS 방식을 활용합니다.

 

---

 

#3. 코드

#include <string>
#include <vector>
#include <map>
#include <unordered_map>
using namespace std;

typedef pair<int, int> p;

p cPos = {0, 0};
map<char, p> d = {
    {'U', {1, 0}},
    {'D', {-1, 0}},
    {'R', {0, 1}},
    {'L', {0, -1}}};

struct Path
{
    p u, v;
    Path(p _u, p _v) : u(_u), v(_v) {}
    ` bool CheckIsVisited(p a, p b)
    {
        if (a == u && b == v)
            return true;
        else if (b == u && a == v)
            return true;
        else
            return false;
    }
};

vector<Path> visitedPath;

int solution(string dirs)
{
    int ans = 0;

    for (int i = 0; i < (int)dirs.size(); ++i)
    {
        int ny = cPos.first + d[dirs[i]].first;
        int nx = cPos.second + d[dirs[i]].second;

        // #1. 벗어난 경로인지 체크
        if (ny < -5 || ny > 5 || nx < -5 || nx > 5)
            continue;

        // #2. 해당 경로 방문 여부 확인
        bool checkIsVisited = false;
        for (auto &path : visitedPath)
        {
            if (path.CheckIsVisited({cPos.first, cPos.second}, {ny, nx}))
                checkIsVisited = true;
        }

        // #3. 경로 카운트 추가 여부 확인 : 새로운 경로 추가 및 경로 카운팅
        if (!checkIsVisited)
        {
            visitedPath.push_back(Path(cPos, {ny, nx}));
            ans++;
        }

        cPos = {ny, nx};
    }

    return ans;
}

 

---