[Softeer](LV 3) 출퇴근길

문제 링크

LV 3: 출퇴근길

구현 방식

• 정방향 간선 edges와 역방향 간선 edges_r를 사용해야한다
• 이 문제는 src -> dest로 정방향 간선을 통해 가는 과정에서 방문한 노드와, dest -> src로 역방향 간선을 통해 가는 과정에서 방문한 노드가 겹친다면, 겹치는 노드들은 src와 dest 사이의 경로에 모두 포함될 수 있는 정점이라는 사실을 이용해주어야 한다

1. S->T로 이동하는 과정을 정방향 간선 edges를 통해 bfs를 수행해주어 visit1을 완성한다
   -> 이때 T는 한번만 방문해야하기 때문에 visit1[T]=True로 미리 설정해줌
2. T->S로 이동하는 과정을 역방향 간선 edges_r을 통해 bfs를 수행해주어 visit1_r을 완성한다
3. T->S로 이동하는 과정을 정방향 간선 edgesf를 통해 bfs를 수행해주어 visit2를 완성한다
   -> 이때 S는 한번만 방문해야하기 때문에 visit2[S]=True로 미리 설정해줌
4. S->T로 이동하는 과정을 역방향 간선 edges_r을 통해 bfs를 수행해주어 visit2_r을 완성한다

• 1번 ~ 4번의 과정을 거쳐 완성한 4개의 visit 리스트들의 교집합을 찾아서 answer를 구해주면 된다

코드

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())
edges = dict(); edges_r = dict()
for m in range(M):
    x, y = map(int, sys.stdin.readline().split())
    if x in edges: edges[x].append(y)
    else: edges[x] = [y]
    if y in edges_r: edges_r[y].append(x)
    else: edges_r[y] = [x]
S, T = map(int, sys.stdin.readline().split())

def bfs(edge, start, end, visit):
    queue = deque([]); queue.append(start)
    
    while queue:
        cur = queue.popleft()
        # if cur == end: continue
        if cur in edge:
            for nxt in edge[cur]:
                if not visit[nxt]:
                    visit[nxt] = True
                    queue.append(nxt)

visit1 = [False]*(N+1); visit1[T] = True
bfs(edges, S, T, visit1) #정방향 간선을 통해 S->T 이동 시 방문하는 노드 구함
visit1_r = [False]*(N+1);
bfs(edges_r, T, S, visit1_r) #역방향 간선을 통해 T->S 이동 시 방문하는 노드 구함

visit2 = [False]*(N+1); visit2[S] = True
bfs(edges, T, S, visit2) #정방향 간선을 통해 T->S 이동 시 방문하는 노드 구함
visit2_r = [False]*(N+1)
bfs(edges_r, S, T, visit2_r) #역방향 간선을 통해 S->T 이동 시 방문하는 노드 구함

# print(visit1); print(visit1_r); print(visit2); print(visit2_r)

answer = 0
for i in range(1, N+1):
    if i == S or i == T: continue
    if visit1[i] and visit2[i] and visit1_r[i] and visit2_r[i]: answer += 1
print(answer)