[코테 - Softeer] 출퇴근길

💡

고려해야할 부분 => 단, 출퇴근길에서 목적지 정점을 방문하고 나면 동환이는 더 이상 움직이지 않는다. 즉, 출근길 경로에 T는 마지막에 정확히 한 번만 등장하며, 퇴근길 경로도 마찬가지로 S는 마지막에 한 번만 등장해야 한다. (출근길 경로에 S는 여러 번 등장해도 되고, 퇴근길 경로에 T는 여러 번 등장해도 된다.)

1. S->T 이동시 방문 노드
2. T->S 이동시 방문 노드
3. S->노드->S, S에서 다시 S로 돌아올 수 있는 노드
4. T->노드->T, T에서 다시 T로 돌아올 수 있는 노드

3,4의 경우 역방향 그래프를 별도로 생성하여 판단해야한다.
출근길, 퇴근길의 경로에서 모두 방문하는 노드는 결국 양방향으로 이루어져있어야 한다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

def dfs(graph, curr, visited):
    if visited[curr] == 1:
        return
    visited[curr] = 1
    for neighbor in graph[curr]:
        dfs(graph, neighbor, visited)
    return

if __name__=="__main__":
    n, m = map(int, input().split())
    graph = [[] for _ in range(n+1)] 
    reversed_graph = [[] for _ in range(n+1)] 
    for _ in range(m):
        v, e = map(int, input().split())
        graph[v].append(e)
        reversed_graph[e].append(v)
    s, t = map(int, input().split())

    # S->T 이동시 방문 노드
    fromS = [0] * (n+1)
    fromS[t] = 1 # t를 미리 방문한 것으로 세팅해서 t를 방문하는 순간 탐색을 종료
    dfs(graph, s, fromS)

    # T->S 이동시 방문 노드
    fromT = [0] * (n+1)
    fromT[s] = 1 
    dfs(graph, t, fromT)

    # S->노드->S, S에서 다시 S로 돌아올 수 있는 노드
    toS = [0] * (n+1)
    dfs(reversed_graph, s, toS)

    # T->노드->T, T에서 다시 T로 돌아올 수 있는 노드
    toT = [0] * (n+1)
    dfs(reversed_graph, t, toT)

    count = 0

    for i in range(1, n+1):
        if fromS[i] and fromT[i] and toS[i] and toT[i]:
            count += 1

    print(count-2) # s, t vertices는 제외하기