[여행 계획 세우기/P2/Python3]

2152번 여행 계획 세우기 P2

 

 

문제
평소 일로 바쁘던 태희는 휴가를 통해 여행을 다녀오기로 하였다. 우선 태희는 사전 조사를 통해서 여행하려는 도시를 N(1 ≤ N ≤ 10,000) 개 선택하였다. 태희는 비행기를 이용하면 충분히 여행할 수 있을 거라 생각했지만, 짐을 꾸리던 중 비행기가 모든 도시들 사이를 다니는 것은 아님을 알게 되었다. 태희는 다시 비행로에 대해 조사를 하였고, 총 M(1 ≤ M ≤ 100,000) 개의 비행로가 존재함을 알게 되었다.
각각의 비행로는 한 방향으로의 서비스만을 제공한다. 태희는 S(1 ≤ S ≤ N) 번 도시에서 시작해서 T(1 ≤ T ≤ N) 번 도시에서 여행을 끝내기로 하였다. 그리고 태희는 도시와 항공로에 대한 정보를 바탕으로 여행 계획을 세우기로 하였다.
도시와 비행로에 대한 정보가 주어졌을 때, S번 도시에서 T번 도시로 여행을 할 때 최대로 방문할 수 있는 도시의 개수를 구하는 프로그램을 작성하시오. 각각의 도시는 여행 중에 몇 번이든 방문할 수 있으며, 같은 항공로를 여러 번 이용할 수도 있다. 물론 같은 도시를 여러 번 방문하는 경우는 한 번만 생각하기로 한다.

입력
첫째 줄에 네 정수 N, M, S, T가 주어진다.
다음 M개의 줄에는 각각의 비행로에 대한 정보를 나타내는 서로 다른 두 정수 A, B(1 ≤ A, B ≤ N)가 주어진다.
이는 A번 도시에서 B번 도시로 이동하는 항공로가 존재함을 의미한다.

출력
첫째 줄에 방문할 수 있는 도시의 최대 개수를 출력한다. 만약 여행 계획을 목표대로 세울 수 없다면 0을 출력한다.

 

다이나믹 프로그래밍, 그래프 이론, 위상 정렬, 방향 비순환 그래프, 강한 연결 요소

 

 

S지점에서 T지점까지의 방문할 수 있는 최대 도시의 수를 구하는 문제이다.

강한 연결 요소인 SCC를 만들어서 시작점이 속한 SCC부터 T가 속한 SCC까지 위상정렬하여 풀이를 진행했다.

 

SCC그룹을 구할 때는 코사라주 알고리즘을 사용했다.

각각의 SCC는 분리 집합을 이용해 하나로 묶었다.

 

import sys
sys.setrecursionlimit(10**6)

n, m, s, t = map(int, sys.stdin.readline().split())

routes = [[] for _ in range(n+1)]
rev_routes =[[] for _ in range(n+1)]
p=[i for i in range(n+1)]
cnt = [1] * (n+1)
dp = [0] * (n+1)
visit = [False] * (n+1)
scc_groups = []
stk = []

for _ in range(m):
    before, after = map(int, sys.stdin.readline().split())
    routes[before].append(after)
    rev_routes[after].append(before)

def find(v):
    if v == p[v]:
        return v
    p[v] = find(p[v])
    return p[v]

def union(v1, v2):
    r1, r2 = find(v1), find(v2)
    if r1 == r2: return
    p[r1] = r2
    cnt[r2] += cnt[r1]

def add_stk_dfs(v):
    visit[v] = True
    for vv in routes[v]:
        if visit[vv]: continue
        add_stk_dfs(vv)
    stk.append(v)
    
def find_scc_dfs(v):
    temp.append(v)
    visit[v] = False
    for vv in rev_routes[v]:
        if not visit[vv]: continue
        find_scc_dfs(vv)
        
add_stk_dfs(s)

for i in range(len(stk)-1, -1, -1):
    v = stk[i]
    if not visit[v]: continue
    temp = []
    find_scc_dfs(v)
    scc_groups.append(temp)
    
for scc in scc_groups:
    v1 = scc[0]
    for v2 in scc:
        union(v1, v2)

while stk:
    v = stk.pop()
    r1 = find(v)
    for vv in routes[v]:
        r2 = find(vv)
        if r1 == r2: continue
        dp[r2] = max(dp[r2], dp[r1] + cnt[r1])

print(dp[find(t)]+cnt[find(t)] if dp[find(t)]+cnt[find(t)] != 1 else 0)

 

cnt는 해당 SCC에 속한 도시의 개수를, dp는 해당 도시까지 가는 데의 최대 도시를 뜻한다.

s 지점에서 dfs를 진행했으나 미방문한 정점을 제외해야 한다.

이를 구분하기 위해 방문여부가 True인 점만 역으로 dfs를 진행할 때 탐색했다.

 

각 scc를 구분하기 위해 Union Find 분리 집합을 사용했다.

 

scc를 찾은 이후 stk에는 진입차수가 0인 애들이 마지막에 들어가 있다.

stk의 pop 되는 정점부터 방문을 진행한다.

 

s에서 t를 방문 못하는 경우는 dp(t 정점까지 오는 경로) + cnt(t가 속한 scc의 도시 개수) == 1이면 방문하지 못하는 경우이다.

 

이를 이용해 예외 케이스까지 처리를 하고 결과를 반환한다.

 

---