[softeer] HSAT 기출 출퇴근길 파이썬 python

문제

이 문제는 내가 풀었던 dfs/bfs 문제중에 가장 까다로웠던 문제였다.

문제의 요점은 출근, 퇴근 길에 모두 방문 가능한 노드를 구하는것

이때 유의할점은 출근할때는 s가 여러번 등장해도 되며 퇴근할 때에는 t가 여러번 등장해도 된다. 다만 목적지는 한번만 등장해야할 것

문제를 풀기위해서 생각한 것은 출근길, 퇴근길 이때 방문하는 노드를 체크해준 후 중복되는 노드의 개수를 세주는 것이다.

그런데 이때 "출근할때는 s가 여러번 등장해도 되며 퇴근할 때에는 t가 여러번 등장해도 된다." 이 조건 때문에 두가지 경우의 수가 더 생긴다

S에서 출발해 여기저기를 돌다가 다시 S에 돌아오는 경우,
T에서 출발해 여기저기를 돌다가 다시 T에 돌아오는 경우

이렇게 총 4가지 경우의 수를 계산해 방문처리를 해준 후
이 4가지 경우에 모두 방문한 노드의 개수를 구해주면 된다

코드

import sys
from collections import deque

def bfs(s,graph,visited):
    q = deque()
    q.append(s)
    visited[s] = 1
    
    while(q):
        now = q.popleft()
        for next in graph[now]:
            if visited[next]:
                continue      
            q.append(next)
            visited[next] = 1




n,m  = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
graph_re = [[] for _ in range(n+1)]

for i in range(m):
    x,y = map(int, sys.stdin.readline().split())
    graph[x].append(y)
    graph_re[y].append(x)
    
s,t = map(int, sys.stdin.readline().split())

#출근
visit1 = [0]*(n+1)
visit1[t] = 1
bfs(s,graph,visit1)
#퇴근
visit2 = [0]*(n+1)
visit2[s] = 1
bfs(t,graph,visit2)

#s->s
visit1_re = [0]*(n+1)
bfs(s,graph_re,visit1_re)
#t->t
visit2_re = [0]*(n+1)
bfs(t,graph_re,visit2_re)

answer = 0
for i in range(1, n+1):
	#목적지와 출발지 노드는 제외
    if i == s or i == t: 
        continue
    if visit1[i] and visit2[i] and visit1_re[i] and visit2_re[i]: 
        answer += 1


print(answer)

정리하자면 이렇게 된다.
구현할 방법을 생각하기가 너무 어려웠던 문제였다. bfs 를 알고있는 사람도 쉽게 생각하기 어려웠던것같다