백준 2644 (C++) 촌수계산

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

2644번: 촌수계산

bfs로 queue에 현재 노드 번호(cur or i)와, 현재 그 노드가 가진 촌수(cnt)를 pair<int,int>형으로 기록하며 넣어주었다.

현재 노드와 다음 노드가 인접하다면 (arr[cur][i] 가 1이라면) queue에 cnt+1하여 push한다.

 

 

10분만에 아래 틀린 코드를 짜놓고 잔뜩 뿌듯해하며 냈는데 33%에서 틀려서 부랴부랴 고쳤다.

 

우선 양방향 그래프로 구현되기에 방문체크가 필요하다. 2-4를 방문하고 4-2를 방문할때 무한 루프에 빠질 수 있다.

그리고 치명적인 실수인데... 총 노드의 개수가 m이 아니라 n이다.!!!!

 

#include <iostream>
#include <queue>
#include <algorithm>
#include <deque>
using namespace std;
const int MAX = 100;
int n,a,b,m;
int arr[MAX][MAX];
bool visited[MAX][MAX];

int bfs() {
    queue<pair<int, int>> q;
    q.push({a,0});
    while (!q.empty()) {
        int cur = q.front().first;
        int cnt = q.front().second;
        if (cur == b) {
            return cnt;
        }
        q.pop();
        for (int i = 1; i <= m; i++) {
            if (visited[cur][i]) {
                continue;
            }
            visited[cur][i] = true;
            if (arr[cur][i]) {
                q.push({i, cnt+1});
            }
        }
    }
    return -1;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> a >> b;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int x,y;
        cin >> x >> y;
        arr[x][y] = 1;
        arr[y][x] = 1;
    }
    cout << bfs();
    return 0;
}

 

 

#include <iostream>
#include <queue>
#include <algorithm>
#include <deque>
using namespace std;
const int MAX = 100;
int n,a,b,m;
int arr[MAX][MAX];
bool visited[MAX][MAX] = {false, };

int bfs() {
    queue<pair<int, int>> q;
    q.push({a,0});
    while (!q.empty()) {
        int cur = q.front().first;
        int cnt = q.front().second;
        if (cur == b) {
            return cnt;
        }
        q.pop();
        for (int i = 1; i <= n; i++) {
            if (visited[cur][i] || visited[i][cur]) {
                continue;
            }
            if (arr[cur][i] == 1) {
                visited[cur][i] = visited[i][cur] = 1;
                q.push({i, cnt+1});
            }
        }
    }
    return -1;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> a >> b;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int x,y;
        cin >> x >> y;
        arr[x][y] = 1;
        arr[y][x] = 1;
    }
    cout << bfs();
    return 0;
}

 

간단한 그래프 탐색 문제였다.