[소프티어 6248번] 출퇴근길

 

# 시간 초과 코드(10/100)

import sys

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

# 동환이의 출퇴근 길은 1~n까지 번호가 매겨진 단방향 그래프
# m개의 일방통행 도로가 존재

# 동환이의 집과 회사는 각각 정점 S, T로 나타냄 (출퇴근길은 S와 T 사이의 경로)

# S에서 T로 가는 출근 경로와 T에서 S로 가는 퇴근 경로에 모두 포함될 수 있는 정점의 개수

# 단, 출퇴근길에서 목적지 정점을 방문하고 나면 동환이는 더 이상 움직이지 않는다.
# 즉, 출근길 경로에 T는 마지막에 정확히 1번만 등장하며 퇴근길 경로도 마찬가지로 S는 마지막에 1번만 등장
# (대신 출근길에 S와 퇴근길에 T와 같이 출발지점은 여러번 등장해도 됨)

n, m = map(int,input().split())

graph = [[] for _ in range(n+1)]
visited = [False]*(n+1)

for _ in range(m):
    start, end = map(int,input().split())

    graph[start].append(end)

S, T = map(int,input().split())

# 탐색 종료 조건 : 목적지 노드 도착

available_go_set = set()
available_back_set = set()
go_node_set = set()
back_node_set = set()

def dfs(n,start,dest):

    if n == dest:
        return

    if n != start:
        if start == S:
            available_go_set.add(n)
        else:
            available_back_set.add(n)
        
    visited[n] = True

    for i in graph[n]:
        if not visited[i]:
            dfs(i,start,dest)

    visited[n] = False

def get_nodes_in_go(n,nodes):

    global go_node_set

    if n == T:
        go_node_set |= nodes
        return

    visited[n] = True

    for i in graph[n]:
        if not visited[i]:
            get_nodes_in_go(i,nodes | {n})

    visited[n] = False

def get_nodes_in_back(n,nodes):

    global back_node_set

    if n == S:
        back_node_set |= nodes
        return

    visited[n] = True

    for i in graph[n]:
        if not visited[i]:
            get_nodes_in_back(i,nodes | {n})

    visited[n] = False

dfs(S,S,T)
dfs(T,T,S)

for i in available_go_set:
    visited = [False]*(n+1)
    get_nodes_in_go(i,{i})

for i in available_back_set:
    visited = [False]*(n+1)
    get_nodes_in_back(i,{i})

go_node_set.discard(S)
back_node_set.discard(T)

print(len(go_node_set & back_node_set))

 

이번 문제는 단방향 그래프와 시작점 S와 도착점 T가 주어졌을 때, S->T 경로와 T->S 경로에 모두 존재하는 즉, 출퇴근길에 겹치는 중간 지점을 구하는 문제이다.(단, 시작점은 여러 번 방문할 수 있지만 도착점은 단 1번만 방문할 수 있다)

 

처음에는 시작점 S/도착점 T과 연결된 모든 중간 지점을 구하고(dfs), 모든 중간 지점에서 시작하여 도착점 T/시작점 S에 도달할 수 있다면 해당 지점들을 출근길(get_nodes_in_go)/퇴근길(get_nodes_in_back) 별로 저장해주었다.

 

하지만 제출해본 결과 테스트케이스는 모두 맞았지만, 다른 테스트케이스에서 시간초과가 발생하게 되었다.

 

그 이유를 분석해보니 나의 풀이는

1. DFS로 시작점/도착점에 연결된 모든 중간 지점들을 구하고 - O(N)
2. 각 중간 지점 별로 DFS를 실행하여 도착지점에 도달하는지 탐색한다 - O(N)

이러한 방식이라 O(N * N) = O(N^2) 의 시간복잡도가 나오게 되고, 입력 값 n은 최대 10^5 이므로 시간초과가 발생할 수 밖에 없게 된다.

# 정답 코드(100/100)

import sys

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

# 동환이의 출퇴근 길은 1~n까지 번호가 매겨진 단방향 그래프
# m개의 일방통행 도로가 존재

# 동환이의 집과 회사는 각각 정점 S, T로 나타냄 (출퇴근길은 S와 T 사이의 경로)

# S에서 T로 가는 출근 경로와 T에서 S로 가는 퇴근 경로에 모두 포함될 수 있는 정점의 개수

# 단, 출퇴근길에서 목적지 정점을 방문하고 나면 동환이는 더 이상 움직이지 않는다.
# 즉, 출근길 경로에 T는 마지막에 정확히 1번만 등장하며 퇴근길 경로도 마찬가지로 S는 마지막에 1번만 등장
# (대신 출근길에 S와 퇴근길에 T와 같이 출발지점은 여러번 등장해도 됨)

n, m = map(int,input().split())

graph = [[] for _ in range(n+1)]
graph_r = [[] for _ in range(n+1)]

answer = 0

for _ in range(m):
    start, end = map(int,input().split())

    graph[start].append(end)
    graph_r[end].append(start)

S, T = map(int,input().split())

# 탐색 종료 조건 : 목적지 노드 도착

def dfs(n,graph,visited):
    if visited[n]:
        return
    visited[n] = True

    for next in graph[n]:
        dfs(next,graph,visited)
    return

visited1 = [False] * (n+1)
visited1[T] = True
dfs(S,graph,visited1)

visited1_r = [False] * (n+1)
dfs(T,graph_r,visited1_r)

visited2 = [False] * (n+1)
visited2[S] = True
dfs(T,graph,visited2)

visited2_r = [False] * (n+1)
dfs(S,graph_r,visited2_r)

for i in range(1,n+1):
    if i == S or i == T:
        continue
    if visited1[i] and visited1_r[i] and visited2[i] and visited2_r[i]:
        answer += 1

print(answer)

 

따라서 시간초과가 발생하지 않기 위해서는 다른 방식으로 풀이해야 하는데, 방법이 떠오르지 않아 해설을 참고하였다.

 

해설에 따르면 이 문제를 해결하기 위해서는 역방향 간선 그래프를 이용해야 한다. 역방향 간선 그래프에서 t가 어떤 정점에 도달할 수 있다는 것은 정방향 간선 그래프에서 그 정점도 t에 도달할 수 있음을 의미하기 때문이다.

 

즉, 역방향 그래프를 하나 더 만들어서 도착지점에서 DFS를 돌려보면 굳이 시작점과 도착점의 중간 지점마다 DFS를 돌릴 필요없이 해당 지점이 도착지점과도 연결되어 있는지 확인할 수 있다는 것이다. ⭐️⭐️

 

이에 따라 도착지점과 연결된 출근길 S->T(정방향)과 T->S(역방향), 시작지점과 연결된 T->S(정방향)과 S->T(역방향) 총 4가지를 모두 만족하는 교집합을 구하면 O(N)의 시간복잡도로 출퇴근길에 겹치는 지점들을 구할 수 있다.