[ BOJ ] 1325 / 효율적인 해킹

문제 

회사를 해킹하려고 합니다.

회사는 N개의 컴퓨터로 이루어져 있습니다.

한 번의 해킹으로 여러 개의 컴퓨터를 해킹할 수 있는 컴퓨터를 해킹하려고 합니다.

 

컴퓨터는 신뢰하는 관계, 신뢰하지 않는 관계로 이루어져 있습니다.

A가 B를 신뢰하는 경우에는 B를 해킹하면 A도 해킹할 수 있는 소리입니다

• A → B 이런 상황이면 화살표를 향한 쪽의 컴퓨터를 해킹해야합니다.

 

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하세요.

 

 

Input

첫 째줄에, n과 m이 들어옵니다

둘 째줄에 m개의 줄에 신뢰하는 관계가 A B 와 같은 형식으로 들어옵니다.

이때 A B 는 A가 B를 신뢰한다는 것을 의미합니다.

컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있습니다.

 

Output

한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력합니다.

 

 

내 생각

• 5 4가 들어왔습니다.
• 4개의 줄에 신뢰하는 관계가 들어옵니다.
  • 3 → 1 : 1을 해킹하면 3도 해킹이 됩니다.
  • 3 → 2 : 2를 해킹하면 3도 해킹이 됩니다.
  • 4→ 3 : 3을 해킹하면 4도 해킹이 됩니다.
  • 5 → 3 : 3을 해킹하면 5도 해킹이 됩니다.
• 이 연결 관계를 어떻게 그래프로 표현할 것인가? 

 

참고

일반적인 그래프 탐색 문제입니다.

BFS 를 이용하여 풀 수 있습니다.

Code