[백준 2644번] 촌수계산

풀이

---

BFS 문제인데 촌수(카운트)를 세줄때 cnt_que를 생성해서 계산해주어야 해결가능했다...

소스 코드

---

#include <iostream>
using namespace std;
 
int n, m, dest_x, dest_y, xy[101][101] = {0,};
int q[10001], head = 0, tail = 0,flag=0,result;
int cnt_q[10001], c_head = 0, c_tail = 0;
void push(int a) {
    q[tail++] = a;
}
 
void c_push(int a) {
    cnt_q[c_tail++] = a;
}
 
int pop() {
    return q[head++];
}
 
int c_pop() {
    return cnt_q[c_head++];
}
 
void bfs() {
    while (1) {
        int start = pop();
        int cnt = c_pop();
        for (int i = 1; i <= n; i++) {
            if (xy[start][i] == 1 || xy[i][start] == 1) {
                push(i);
                c_push(cnt + 1);
                xy[start][i] = cnt+1;
                xy[i][start] = cnt+1;
                if (i == dest_y) {
                    result = cnt;
                    return;
                }
            }
        }
        if (head == tail) {
            flag = 1;
            break;
        }
    }
}
 
int main() {
    cin >> n >> dest_x >> dest_y >> m;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        xy[x][y] = 1;
        xy[x][y] = 1;
    }
    push(dest_x);
    c_push(2);
    bfs();
    
    if (flag)
        cout << -1 << '\n';
    else
        cout << result-1 << '\n';
    return 0;
}