반응형
https://www.acmicpc.net/problem/1325
1325번: 효율적인 해킹
첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한
www.acmicpc.net
소스코드
풀이
★ 정답률이 엄청 낮길래 왜그런지 궁금했는데, 시간초과랑 메모리 초과가 많이 떠서 그랬던 거 같습니다 !
제 코드도 Python으로 채점하면 시간 초과가 뜨고, pypy로 채점해야지 통과가 되더라구요
★ 일반적인 BFS 그래프 탐색문제입니다. 주의해야 할 부분은 보통 간선 문제의 경우에는 A와 B가 주어졌을 경우 A -> B로 가는 경우가 대부분인데 이번 문제는 B -> A로 방향이 갑니다
★ 또한 탐색한 점을 체크하는 배열 (visited)를 계속 초기화 해줘야 합니다 ! 그 이유는 한번에 가장 많이 해킹할 수 있는 컴퓨터를 찾기 위해서 컴퓨터 번호 하나당 경우의 수를 다 찾아야하기 때문입니다 !
반응형
'Algorithm > 백준' 카테고리의 다른 글
| [백준 알고리즘] 1743번: 음식물 피하기 (Python, BFS) (0) | 2023.10.04 |
|---|---|
| [백준 알고리즘] 2910번: 빈도 정렬 (Python) (0) | 2023.10.04 |
| [백준 알고리즘] 25192번: 인사성 밝은 곰곰이 (Python) (0) | 2023.10.02 |
| [백준 알고리즘] 1926번: 그림 (Python, BFS) (0) | 2023.09.28 |
| [백준 알고리즘] 2606번: 바이러스 (Python) (0) | 2023.09.22 |