[백준 14496번] 그대, 그머가 되어 (C++)

문제링크 : https://www.acmicpc.net/problem/14496

14496번: 그대, 그머가 되어

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

vector<int> arr[1001];
bool check[1001];

int bfs(int start, int end)
{
    queue<pii>q;
    q.push({start, 0});  //시작점과 초기 카운트 값

    while(!q.empty())
    {
        int cur = q.front().first;  //현재 문자
        int cnt = q.front().second; //현재 치환 횟수
        q.pop();

        if(cur == end)  //치환을 성공했다면
        {
            return cnt;
        }

        for(int i=0; i<arr[cur].size(); i++)
        {
            int next = arr[cur][i];  //다음 문자
            if(check[arr[cur][i]]) continue;
            check[arr[cur][i]] = true;
            q.push({next, cnt+1});  //다음 문자에 대해 탐색하며 치환 횟수 증가
        }
    }
    return -1;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int a, b;
    cin >> a >> b;
    int N, M;
    cin >> N >> M;
    while(N--)
    {
        for(int i=0; i<M; i++)
        {
            int s, e;
            cin >> s >> e;
            arr[s].push_back(e);
            arr[e].push_back(s);
        }
    }
    
    int result = bfs(a, b);  
    cout << result;

    return 0;
}

bfs탐색을 통해 풀었다.

큐에 시작점과 치환 횟수를 같이 넘겨준다.

 

처음 문자 a가 원하는 문자 b까지 도달할때까지 치환이 몇 번이나 이루어졌는지를 검토한다.

처음 문자 a에 대해 연결된 값들을 검토하고 연결된 값들에 대해 계속해서 연결된 값들이 있는지를 확인하며 연결된 것을 확인할때 마다 치환 횟수가 1 증가한다.

최종적으로 연결된 값이 b라면 치환을 성공한 것이기에 여태까지 증가시켰던 최종 횟수를 반환하지만, 만약 최종적으로 연결된 값이 다른 값이라면 치환을 실패한 것이므로 반복문이 종료되며 -1를 반환한다.