[Softeer] S1529 출퇴근길

[Softeer]

Question

Language: Python

dfs을 활용하여 출근길, 퇴근길 경로에 중복으로 포함되는 노드의 갯수를 구하는 문제이다. 이때, 단순히, start -> end, end -> start 과정만 고려하게 되면 문제가 발생하게 된다.

아래의 그래프를 예시로 보자

1.출발지에서 목적지까지 경로에서 도달 가능한 노드: [1,2,3,4,5] 2.목적지에서 출발지까지의 경로에서 도달가능한 노드: [1,2,3,4,5]

하지만 4,5번 노드를 출발하여 목적지 노드에 도달하는 것이 불가능하다. 즉, 경로 내에 노드가 포함되지 않는다는 의미이다. 그러면 중간 노드에 대해 다시 dfs을 수행해야될까? 그러면 모든 중간 노드에 대해 다시 dfs을 수행해야하므로 이는 주어진 시간 내에 문제풀이가 불가능하다. 이때, 역방향 그래프를 활용한다.

역방향 그래프 dfs

특정 노드에 대해 역방향 그래프 dfs을 수행하게 되면 특정 노드에 도달할 수 있는 중간 노드를 구할 수 있다.

3.출발지를 기준으로 dfs 실행한 경우: [1,2,3] 4.목적지를 기준으로 dfs 실행한 경우: [1,2,3]

위의 정방향 그래프 dfs을 통해 얻은 결과 1,2와 역방향 그래프 dfs을 통해 얻은 결과 3,4을 조합하면 오직 2번 노드만이 중복되는 것을 확인할 수 있다(출발지, 목적지 제외)

Solution

import sys 

def DFS(now, adj, visit):
    if visit[now]==1:
        return
    else:
        visit[now]=1
        for neighbor in adj[now]:
            DFS(neighbor, adj, visit)
    return

if __name__=="__main__":
    sys.setrecursionlimit(10**6)

    n,m=map(int, input().split())   # 정점, 간선 
    adj=[[] for _ in range(n+1)]    # 노드별 이동 가능한 노드들 정보
    adjR=[[] for _ in range(n+1)]   # adj_reverse
    for _ in range(m):
        a,b=map(int,input().split())
        adj[a].append(b)    # a노드에서 b노드로 갈수 있음
        adjR[b].append(a)
    S,T=map(int, input().split())   # S->T S가 집 T가 회사

    # 목적: S->T와 T->S로 모두에서 방문 가능한 정점의 개수를 출력한다.
    fromS=[0]*(n+1)
    fromS[T]=1          # S->T 1로 미리 세팅
    DFS(S,adj,fromS)

    fromT=[0]*(n+1)
    fromT[S]=1          # T->S 1로 미리 세팅
    DFS(T,adj,fromT)

    toS=[0]*(n+1)
    DFS(S,adjR,toS)

    toT=[0]*(n+1)
    DFS(T,adjR,toT)
    
    count=0
    for i in range(1,n+1):
        if fromS[i] and fromT[i] and toS[i] and toT[i]: # 이렇게가는거랑 저렇게 가는거랑 모두 1일때만
            count+=1

    print(count-2)