[C++] 백준 2644번: 촌수계산

문제

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

 

풀이

 

당연히 DFS로 풀어야 한다고 생각했는데 BFS로 푸는 사람이 더 많은 것 같다.. 

촌수는 깊이 아니냐고....... 왜 BFS로 푸는게 더 좋다고 하는거지? 아는 사람 알려주기  약속~~

 

---

촌수 관계를 담는 그래프 

 

평소처럼 2차원 배열로 하려다가 어떤 블로그에서 이렇게 하길래 따라 해봤다.

//전역
std::vector<std::vector<int>> graph;

//main문
graph.assign(n+1,std::vector<int>(0, 0));

 

 

DFS

bool DFS(int v)
{
    if(v == b) return true;
    ++result;
    visited[v] = true;
    
    //연결된 노드만 탐색
    for(int i=0; i <graph[v].size(); ++i)
    {
        //방문하지 않은 노드가 있다면
        if(!visited[graph[v][i]])
        {
            //탐색 시작
            if(DFS(graph[v][i])) return true;
            else --result;
        }
    }
    
    return false;
}

 

 

graph[v][i]가 좀 복잡해보이지만 그냥 연결된 노드일 뿐이다.  v=2인 예가 아래다. 

graph[2].size() = 4

graph[2][0] = 1
graph[2][1] = 7
graph[2][2] = 8
graph[2][3] = 9


visited[graph[2][0]] = visited[1]

 

 

visited[연결된 노드]가 아직 방문되지 않았다면 DFS(연결된 노드)를 호출하여 재귀함수로 사용한 것이다. 

if(DFS(graph[v][i])) return true;
else --result; // 이어지는 촌수가 없다면 다시 촌수 올라가야하니까 빼줌

• DFS(연결된 노드) 가 true라면 if(v==b)를 만나 이미 촌수를 찾은 것이다. 재귀함수를 종료시켜도 된다. 
• DFS(연결된 노드) 가 false라면 한 노드를 따라 들어갔지만 촌수를 찾을 수 없어서 같은 레벨로 다시 돌아왔다는 뜻이다. 그래서 촌수를 감소시켜야 한다.  이해가 안 간다면 예제 2를 그래프로 그리고 첨부한 코드를 따라 눈디버깅해보세요..

 

 

 

BFS

bool BFS(int v)
{
    std::queue<int> q;
    q.push(v);
    visited[v] = true;
    
    while(!q.empty())
    {
        int qSize = q.size();
        for(int j =0; j<qSize; ++j)
        {
            int data = q.front(); q.pop();
            if(data == b) return true;
            
            for(int i=0; i<graph[data].size(); ++i)
            {
                if(!visited[graph[data][i]])
                {
                    q.push(graph[data][i]);
                    visited[graph[data][i]] = true;
                }
            }
        }
        result++;
    }
    return false;
}

촌수 세다가 서치 해봤는데 다들 쓰는 pair 쓰기 싫어서 오기 부리다가 시간을 많이 소비했지만 어쨌든 성공한 소스.

queue를 사용하여 전에 풀었던 숨바꼭질처럼 풀었다. (블로그 참고)

BFS는 그래프의 한 레벨이 촌수라 한 레벨을 다 탐색한 후 촌수를 증가시키면 된다. 

(해당 문제는 부모가 한명 뿐이라 트리 형식이기 때문에 레벨로 따질 수 있음)

 

큐의 데이터 중 어디까지가 한 레벨의 노드들인지 구별하기 위해서 while문을 하나 더 감쌌다. 

    while(!q.empty()) // 이게 없으면 무한 루프
    {
        int qSize = q.size(); // qSize는 현재 레벨의 노드 개수를 가지고 있다. 
        for(int j =0; j<qSize; ++j)
        {
            // q.size()가 커지는 조건문이 있다. 
        }
        result++; // 촌수 
    }

 

 

 

 

도움이 됐던 백준에서 주운 반례 케이스 

4
4 2
3
2 3
3 1
3 4

 

소스

main문에서 DFS(), BFS() 주석 골라서 실행 가능~~

 

#include <iostream>
#include <vector>
#include <queue>
 
#define MAX 100
 
std::vector<std::vector<int>> graph;
bool visited[MAX+1];
int n, a, b, m;
int result = 0;
 
bool DFS(int v)
{
    if(v == b) return true;
    ++result;
    visited[v] = true;
    
    //연결된 노드만 탐색
    for(int i=0; i <graph[v].size(); ++i)
    {
        //방문하지 않은 노드가 있다면
        if(!visited[graph[v][i]])
        {
            //탐색 시작
            if(DFS(graph[v][i])) return true;
            else --result;
        }
    }
    
    return false;
}
 
bool BFS(int v)
{
    std::queue<int> q;
    q.push(v);
    visited[v] = true;
    
    while(!q.empty())
    {
        int qSize = q.size();
        for(int j =0; j<qSize; ++j)
        {
            int data = q.front(); q.pop();
            if(data == b) return true;
            
            for(int i=0; i<graph[data].size(); ++i)
            {
                if(!visited[graph[data][i]])
                {
                    q.push(graph[data][i]);
                    visited[graph[data][i]] = true;
                }
            }
        }
        result++;
    }
    return false;
}
 
int main()
{
    int x, y =0;
    std::cin >> n >> a >> b >> m;
    
    graph.assign(n+1,std::vector<int>(0, 0));
    
    while(m--)
    {
        std::cin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    
    //std::cout << (DFS(a) ? result : -1);    
    std::cout << (BFS(a) ? result : -1);
    
    return 0;
}