그대, 그머가 되어 - 14496

문제

https://www.acmicpc.net/problem/14496

느낀점

한 번 변환할 때마다 변환 횟수를 기록해주어야하는데 그 과정을 bfs로 구현했다. 처음에는 생각해내는 것이 어려웠는데, bfs 문제를 풀다보면 비슷한 패턴으로 풀 수 있다. 관련 문제를 많이 접해보자!

풀이

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

int main()
{
    int a, b;
    std::cin >> a >> b;
    int N, M;
    std::cin >> N >> M;
    std::map<int, std::vector<int>> change;
    std::queue<std::pair<int, int>> stack;
    std::vector<int> count(N + 1, 0);
    std::vector<bool> visited(N + 1, false);

    for (int i = 0; i < M; i++)
    {
        int start, end;
        std::cin >> start >> end;
        change[start].push_back(end);
        change[end].push_back(start);
    }

    stack.push(std::make_pair(a, 0));

    while (!stack.empty())
    {
        std::pair<int, int> temp = stack.front();
        visited[temp.first] = true;
        stack.pop();
        if (temp.first == b)
        {
            std::cout << temp.second;
            return 0;
        }

        for (int i = 1; i <= N; i++)
        {
            if (!visited[i] && find(change[temp.first].begin(), change[temp.first].end(), i) != change[temp.first].end())
            {
                visited[i] = true;
                stack.push(std::make_pair(i, temp.second + 1));
            }
        }
    }

    std::cout << -1;
    return 0;
}