[softeer] lv3 출퇴근길_python

이 문제는 정말 까다로웠다. 정확히는 지금 내 수준으로 시간내에 풀기에는 무리가 있었다.
그래서 제공되는 해설을 한번 보고 풀이를 진행했다.

문제는 간단하다. 마을 수 n(정점 수)이 주어지고, 갈수있는 길 m(간선 수)이 주어진다.
그리고 쭉 간선이 m개 만큼 주어지고 마지막에 시작과 끝이 주어진다.
구해야할건 시작점에서 끝점, 그리고 끝점에서 다시 시작점으로 돌아올 때 출근길에 방문하고 퇴근길에 다시 방문할 수 있는 마을의 수를 구하는 것이다. 말로는 이해가 어렵다. 그림을 보면 쉽다.

그림에서 1번 마을에서 3번 마을로 출근한다. 그리고 다시 3번 마을에서 1번 마을로 퇴근한다.
길은 많다. 여기서 dfs를 생각하긴 했다. (정점과 간선이 나오면 dfs라고 생각하는 편)
그런데 길의 갯수를 구하는게 아닌 경유하는 마을을 구하는거다. 물론 [출퇴근길에 중복하여 방문] 이란 조건이 있는...
그림에서 보면 출근길은 1-4-3, 퇴근길은 3-4-1 이렇게 4번 마을을 중복하여 방문하고 그외에는 없다는 것을 알 수 있다.
여기서, 어려운 점은 출근길엔 시작점을 무한 방문 가능하고 끝점을 마지막 단 한번만 방문해야한다. 그 반대도 마찬가지다.

풀이)
우선, 입력을 받아 adj를 만들었다.
1번에서 3번으로 가는 길, 3번에서 1번으로 가는길을 각각 dfs해준다. 물론 visit는 각각 생성했다.
그리고 그 반대의 경우도 생성해서 똑같이 반복한다. 즉, 4개의 visit 리스트가 생성되고
각 마을 방문이 4개 리스트에서 일어나는지 알아보면 된다.
그리고 python 재귀가 약 1000개 정도의 limit이 걸려있기에 10만 이상으로 돌도록 설정해줘야 런타임에러가 안난다.

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
# n 정점, m 간선 수
n, m = map(int, input().split())
adj = [[] for _ in range(n+1)]
adjR = [[] for _ in range(n+1)]
for _ in range(m):
    s, t = map(int, input().split())
    adj[s].append(t)
    adjR[t].append(s)
s, t = map(int, input().split())

def dfs(start, adj, visit):
    if visit[start]:
        return
    visit[start] = 1
    for nxt in adj[start]:
        dfs(nxt, adj, visit)
    return
    
start_S = [0] * (n+1)
start_S[t] = 1
dfs(s, adj, start_S)

start_T = [0] * (n+1)
start_T[s] = 1
dfs(t, adj, start_T)

toS = [0] * (n+1)
dfs(s, adjR, toS)

toT = [0] * (n+1)
dfs(t, adjR, toT)


cnt = 0
for i in range(1, n+1):
    if start_S[i] and start_T[i] and toS[i] and toT[i]:
        cnt += 1
print(cnt-2)

어렵다...