[BOJ1325] 효율적인 해킹

문제

• 해커 김지민, 한 번의 컴퓨터 해킹으로 여러 대 해킹
• 컴퓨터 간 신뢰관계, A가 B 신뢰한다면 B 해킹시 A도 함께 해킹
• 신뢰관계가 주어졌을 때, 한 번에 가장 많이 해킹할 수 있는 컴퓨터 번호 출력

입력

• 첫째 줄, N (1<= <= 10,000) M (1<= <=100,000)
• 둘째 줄부터 M개의 줄에 신뢰관계

출력

• 지민이 가장 많이 해킹할 수 있는 컴퓨터 번호 오름차순 출력

설계

• 단방향 그래프 구현 (벡터 배열)
• BFS 구현하여 방문 노드 수 체크
• 최대로 방문한 경우들 오름차순 출력

피드백

• 문제가 꽤나 쉬웠는데 정답률이 20%밖에 안 되어서 이해가 안 됐음
• 근데 한 번에 못 품…
• BFS로 탐색하며 방문할 수 있는 최대 Depth를 구해서 틀렸음
• Depth 가 아니라 queue에 들어가는 노드 수를 모두 구해서 max값 찾기
• 나는 매번 max값 비교하는 방식을 썼지만, 노드 n에서 시작하여 방문하는 노드 수를 그냥 배열에 담고 최대 방문 수에 해당하는 index 출력하는 게 더 깔끔함

How I solved(click to github)

---

ref :
BOJ1325