🎀 본 게시물은 Softeer 연습문제 풀이 게시물입니다. 🎀

---

https://softeer.ai/practice/info.do?idx=1&eid=1529

정답영상

<!–

–>

문제 설명을 더 하자면

출력예제1의 경우 노드 4, 4번 노드만 출퇴근길 모두 방문 가능한 위치로 딱 하나만 가능하므로

출력예제1 값은 1이다.

---

🚀 정답 ⭕

import sys 
# sys.stdin=open('input.txt','r')

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

if __name__=="__main__":
    n,m=map(int, input().split())   # 정점, 간선 
    adj=[[] for _ in range(n+1)]    # 노드별 이동 가능한 노드들 정보
    adjR=[[] for _ in range(n+1)]   # adj_reverse
    for _ in range(m):
        a,b,=map(int,input().split())
        adj[a].append(b)    # a노드에서 b노드로 갈수 있음
        adjR[b].append(a)
    S,T=map(int, input().split())   # S->T S가 집 T가 회사

    # print(adj)
    # print(adjR)

    # 목적: S->T와 T->S로 모두에서 방문 가능한 정점의 개수를 출력한다.
    fromS=[0]*(n+1)
    fromS[T]=1          # S->T 1로 미리 세팅
    DFS(S,adj,fromS)

    fromT=[0]*(n+1)
    fromT[S]=1          # T->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]: # 이렇게가는거랑 저렇게 가는거랑 모두 1일때만
            count+=1

    print(count-2)

이런문제를 스스로 풀수있는 날이 올까?

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기