[BOJ_1325] 효율적인 해킹

 

📌 문제 링크: https://www.acmicpc.net/problem/1325

1325번: 효율적인 해킹

 

❌ 내 풀이(Failure) :

깊이 우선 탐색(DFS)를 이용한 풀이

 

✅ 내 풀이(Success) :

너비 우선 탐색(BFS)를 이용한 풀이

 

🧐 Review:

 '깊이 우선 탐색'을 이용해서 문제를 해결하려고 시도했지만, 위의 이미지처럼 계속해서 실패했다. 코드를 최대한 최적화했다고 생각했는데 번번이 실패해서 '깊이 우선 탐색'이 아닌 '너비 우선 탐색'을 이용해서 코드를 다시 작성했다. 그러자 이번에는 '시간 초과'가 발생했고, 제출 언어를 PyPy3로 변경하고 제출했을 때 드디어 이 문제를 해결할 수 있었다.

문제를 풀고나서 Python3로 제출했고 문제를 맞힌 풀이가 있는지 확인했는데, 약 5페이지 정도를 확인했지만, 모두 PyPy3로 제출된 풀이밖에 없었다. 앞으로는 '그래프 탐색' 문제를 풀 때 에러가 발생한다면 다른 '그래프 탐색'방법으로 빨리 바꿔서 문제를 풀어보는 것이 좋겠다.

 

🚩 Idea:

 'A가 B를 신뢰한다 -> B를 해킹하면, A도 해킹할 수 있다' 라는 문장을 보고, 그래프가 '단방향 그래프'라는 것을 느꼈다면 아이디어를 떠올리는 것은 어렵지 않았을 것이라고 생각한다.