[알고리즘][BFS] 효울적인 해킹(백준) - 시간 초과

BFS 알고리즘 - 효율적인 해킹 문제 (백준)

하.... 런타임 에러 찾느라고 밤을 꼬박 샌 문제..

결국에 찾긴 했는데 정말 사소한 문제라 더더 기억에 남을만한 문제이다.

런타임 에러 문제를 해결하고 나니 시간초과.. 정답률도 상당히 낮은 나름 어려운 문제였지만

BFS 문제를 상당히 오랜만에 풀어본 것도 나름 원인중 하나였던 것 같다.

효율적인 해킹 , 시간 초과

01. 변수 선언, 초기화

02. bfs 알고리즘

03. 메인 함수

런타임 에러가 난 이유는 내가 큐를 읽고 쓰는 데에 wp, rp라는 변수를 통해서 접근을 했다.

큐를 한번 쓰고 다시 쓰기전에 이 변수들을 초기화해줘야 하는데 이 부분을 잊어 버렸다..

때문에 이 변수들이 큐의 범위를 넘어서 버린 것... 하.... 이것 때문에 몇시간을 고민했는지..

암튼 이 문제를 풀기위해 생각한 방법은

먼저 모든 컴퓨터 목록을 배열에다가 저장하고,

1번 컴퓨터부터 차례로 큐에 넣은 다음 연관있는 모든 컴퓨터들을 큐에다 넣고 조사하는 방식을 선택했다.

이렇게 문제를 풀면서도 상당히 비효율적이라 생각이 들어서 동적 계획법을 살쩍 섞어 볼까도 생각했었다..

하지만 조합하는 도중에 포기하고 원래 방식대로 모든 목록을 순회하는 방식을 사용..

역시나 시간초과.. 다른 이들은 어떻게 풀었나 궁궁해서 슬며시 찾아보니.. 

벡터를 사용한 기가막힌 방법이 있어서 그 방식을 연구해보았다.

다음 포스팅에서 벡터로 이 문제를 멋지게 해결한 방법을 알아보겠다.