백준 알고리즘 1325번 - 효율적인 해킹

dfs로 푸는 문제 노드를 하나씩 돌면서, 각각의 노드가 갈 수 있는 최대 횟수를 벡터에 저장한다. 처음에는 배열로 만들었지만, 최대 크기가 10000*10000이나 되서, 연결 여부를 배열로 만들면 시간 초과가 나온다. 또, 방문 여부를 판단하는 배열을 한 번씩 돌 때마다 초기화 시켜주어야 한다. 처음에는 초기화 시켜주지 않았지만, 최대길이가 짧은 노드부터 방문하게 된다면 최대 방문 순위를 재대로 셀 수 없게 된다. 풀이 과정 1. vector 배열을 만들어, from을 index로, to를 vector 배열에 push 한다. 2. 연결된 두 쌍을 찾아, dfs를 돌린다. 그 후 진행하는 횟수를 arr배열에 저장한다. 3. 오름차순 정렬이므로, arr배열에서 max값을 찾아 그와 동일한 값을 갖는 배열..

2019.07.17