[Softeer] HSAT 6회 기출 - 출퇴근길

문제

<배경>

자동차로 출퇴근을 하는 현서는 지루하지 않게 종종 길을 바꿔 다니곤 한다. 새로운 동네를 발견하는 일은 현서의 소소한 행복이다.

현서의 출근길과 퇴근길은 가끔 겹친다. 즉, 출근길에 들른 동네를 퇴근길에 다시 지나곤 하는 것이다. 이에 대해 곰곰이 생각하던 현서는 이렇게 두 번 들를 수 있는 동네가 그렇게 많지 않음을 깨달았다. 도로의 연결 모양, 그리고 일방통행 여부 등으로 인해 출퇴근길 모두 방문 가능한 동네가 한정되는 것이다.

현서의 출퇴근길은 단방향 그래프로 나타낼 수 있다. 즉 각 동네를 $1$부터 $n$까지의 번호가 매겨진 $n$개의 정점으로, $m$개의 일방통행의 도로를 단방향 간선으로 삼아 그래프를 만들 수 있다. 이때 현서의 집과 회사가 각각 정점 $S$와 $T$로 나타난다고 하면 출퇴근길은 $S$와  $T$사이의 경로로 나타난다.

현서의 출퇴근길을 본딴 그래프가 주어지면 $S$에서 $T$로 가는 출근길 경로와 $T$에서 $S$로 가는 퇴근길 경로에 모두 포함될 수 있는 정점의 개수를 세는 프로그램을 작성하시오. 단, 출퇴근길에서 목적지 정점을 방문하고 나면 현서는 더 이상 움직이지 않는다. 즉, 출근길 경로에 $T$는 마지막에 정확히 한 번만 등장하며, 퇴근길 경로도 마찬가지로 $S$는 마지막에 한 번만 등장해야 한다.

 

<입력>

<출력>

첫째 줄에 출근길과 퇴근길 모두에서 방문 가능한 정점의 개수를 출력한다.

 

<예시>

예제2: 출퇴근길에 모두 방문 가능한 점은 다음의 네 개이다: 1, 2, 3, 7.

---

풀이

아이디어는 꽤 간단하다.

총 4개의 배열을 만든다.

각각

출발지에서 도달할 수 있는 노드,

도착지에서 도달할 수 있는 노드,

출발지로 갈 수 있는 노드,

도착지로 갈 수 있는 노드이다.

이 네 가지 배열은 dfs로 채우면 되고, 이 네가지에 모두 해당되는 노드의 개수를 세고 2를 빼면 된다.

2를 빼는 이유는 출발지와 도착지도 세졌기 때문이다.

import sys
sys.setrecursionlimit(10**6)    

n,m=map(int,input().split())
adj = [[] for _ in range(n+1)] #번호 1부터로 맞춰주기
adjR = [[] for _ in range(n+1)] #간선 방향 바꾼 그래프
for _ in range(m):
    x,y=map(int,input().split())
    adj[x].append(y)
    adjR[y].append(x)
s,t = map(int,input().split())

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

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

fromT = [0]*(n+1)
fromT[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]:
        count += 1
print(count-2)#출발.도착은 빼고 하기위해