2644 촌수계산 BFS (성공)

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

#include<iostream>
#include<cstring>
#include<queue>
 
using namespace std;
 
const int MAX = 100;
 
int n;
int src, dest;
int m;
bool arr[MAX + 1][MAX + 1];
int visited[MAX + 1];
 
void BFS() {
    queue<int> q;
    q.push(src);
    visited[src] = 0;
 
    while (!q.empty()) {
        int now = q.front();
        q.pop();
 
        if (now == dest)
            return;
 
        for (int i = 1; i <= n; i++) {
            if (arr[now][i] == true && visited[i] == -1) {
                q.push(i);
                visited[i] = visited[now] + 1;
            }
        }
    }
}
 
int main() {
    int a, b;
 
    cin >> n;
    cin >> src >> dest;
    cin >> m;
 
    memset(visited, -1, sizeof(visited));
 
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        arr[a][b] = arr[b][a] = true;
    }
 
    BFS();
 
    cout << visited[dest] << endl;
 
    return 0;
}

* 배운점

1)

visited배열을 bool 형이 아닌, int 형으로 선언하고 -1 로 초기화함으로써,

단순히 방문 여부를 표시한 것뿐만 아니라, S(start)지점으로부터 D(destination)지점까지의 거리를 저장하도록 했다.

2)

전역변수와 지역변수 정의해 놓은 본인만의 규칙이 깔끔하다. 배워야지.

문제에서 주어진 변수만을 전역변수로 선언하고,

나머지 문제 풀면서 필요에 의해 만들어진 변수는 지역변수로 정의한 것 같다.

<내 코드>

#include<iostream>
#include<cstring>
#include<queue>
 
using namespace std;
 
int N;
int S, D;
int R;
int x, y;
bool arr[101][101];
int visited[101];
 
int main() {
    queue<int> q;
    int current;
    
    memset(visited, -1, sizeof(visited));
 
    int cnt = 0;
 
    cin >> N;
    cin >> S >> D;
    cin >> R;
    
    for (int i = 0; i < R; i++) {
        cin >> x >> y;
        arr[x][y] = arr[y][x] = 1;
    }
 
    q.push(S);
    visited[S] = 0;
 
    while(!q.empty()) {
 
        current = q.front();
        q.pop();
        /*
        if (current == D) {
 
        for (int i = 1; i <= N; i++) {
            if (arr[current][i] == 1 && visited[i] == -1) {
                q.push(i);
                visited[i] = visited[current] + 1;
            }
        }
    }
 /*
    if (visited[D] == -1)
        cout << -1;
    else
        cout << visited[D];
*/
    cout << visited[D];
 
    return 0;
}

3) 

저렇게 if문으로 조건걸지 않아도 맞았습니다 뜨네.

while문 안에

if (current == D) {

cout << visited[D];

break;

} 

처음에 이렇게 엔딩조건 넣어주니까, 연결되지 않은 정점에 대해 조사할 때 -1 을 출력하는 조건처리가 안되어 틀렸습니다 가 떴음.