[BOJ/백준] 16947 서울 지하철 2호선

● [문제번호 16947] 서울 지하철 2호선

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

16947번: 서울 지하철 2호선

 

● 알아야 할 것

: vector 자료구조와 메소드

: BFS

: DFS (재귀)

 

● 풀이 과정

: 문제를 보고나서 순환선은 Two Dots 문제처럼

시작역에서 출발하여 최소 3개역 이상 거쳐

다시 시작역으로 돌아오는 경우

순환선으로 알아낼 수 있다고 생각이 들었다.

 

그런데 지선은 어떻게 알아낼까?

지선임을 알아내는 건 위와 같은 방법으로 알아낼 수 있지만,

시작역에서 순환선까지 최소 거리를 어떻게 알아낼지 의문이었다.

 

괜찮은 방법이 떠오르지 않아 구글링을 해보니

방법은 다음과 같았다.

 

1. 순환선을 찾아서 순환선에 있는 역을 체크해둔다. (DFS 재귀)

2. 출력을 하는데 (BFS)

2-1. 순환선이면 바로 0출력

2-2. 지선이면 순환선까지 거리를 구해 출력

 

이러한 방법을 떠올리지 못한 이유는

하나의 함수 실행에서

순환선이면 0을 출력하고

지선이면 순환선까지 거리를 출력할 수 있는

일관된 함수를 구현하려고 해서 어려웠던 것 같다.

 

● 주의 할 것

: 순환선인지 찾을 때

순환선이 아닌 곳을 간 경우

체크아웃을 꼭 해야한다.

 

● 참고 할 것

: NULL

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// subway : 각 지하철역의 노선 정보
// visited : (true : 순환선인 지하철역 / false : 지선인 지하철역)
vector<int> subway[3001];
bool visited[3001];
int N;

// 깊이 우선 탐색 (시작역, 현재역, 재귀 깊이)
// 순환선을 찾기 위해 실행
bool dfs(int start, int from, int cnt)
{
    // 현재역 체크인
    visited[from] = true;
    
    for(int i = 0; i < subway[from].size(); i++)
    {
        int to = subway[from][i];
        
        // 시작역으로 다시 돌아 온 경우
        // (다음역 == 시작역)
        // 순환선은 최소 3개의 역이 필요
        if(3 <= cnt && to == start)
            return true;
        else if(!visited[to])
            if(dfs(start, to, cnt + 1))
                return true;
    }
    
    // 순환선만 체크하기 위해 현재역 체크아웃
    visited[from] = false;
    
    return false;
}

// 넓이 우선 탐색 (시작역)
// 지선에서 순환선까지 최소 거리 반환
int bfs(int start)
{
    queue<int> q;
    // 각 지선의 최소거리(방문기록)
    int visitedBFS[3001] = {0, };
    
    visitedBFS[start] = 1;
    q.push(start);
    
    while(!q.empty())
    {
        int from = q.front();
        
        q.pop();
        
        for(int i = 0; i < subway[from].size(); i++)
        {
            int to = subway[from][i];
            
            // BFS함수에서 이미 방문한 적 있는 경우
            if(visitedBFS[to] != 0)
                continue;
            // 순환선을 만난 경우
            else if(visited[to])
                return visitedBFS[from];
            else
            {
                // 최소거리 기록 + Queue 추가
                visitedBFS[to] = visitedBFS[from] + 1;
                q.push(to);
            }
        }
    }
    
    // 여기까지 실행된다면
    // 시작역은 역으로 이어져 있지 않다
    // 따라서 여기까지 올 일 없음
    return -1;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    // 역의 개수 입력
    cin >> N;
    
    // 구간의 정보 입력
    for(int n = 0; n < N; n++)
    {
        int a, b;
        cin >> a >> b;
        
        subway[a].push_back(b);
        subway[b].push_back(a);
    }
    
    // 순환선 찾기
    for(int i = 1; i <= N; i++)
        if(dfs(i, i, 1))
            break;

    // 순환선이면 0 출력
    // 지선이면 순환선까지 (최소)거리 출력
    for(int i = 1; i <= N; i++)
        if(visited[i])
            cout << "0 ";
        else
            cout << bfs(i) << " ";
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [601 - 그래프 1 (연습)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	16929	Two Dots	https://pirateturtle.tistory.com/278
2	16947	서울 지하철 2호선	https://pirateturtle.tistory.com/279