경주로 건설1 경주로 건설 - 카카오 2020 C++ DFS 코딩테스트 풀이 다들 BFS풀고 공식해설도 BFS로 풀었다. BFS로 풀든 DFS로 풀든 상관 없지만 핵심은 완전탐색 과 메모이제이션 이 있어야 시간초과가 나지 않고 정답을 맞출수있다. 완전탐색이라는 방향에서 BFS나 DFS어느것으로 풀어도되는데 많은 블로그에서 DFS로 풀면 틀린다는 듯이 말을 해서 풀이를 올리게 되었다. 충분히 짧은 시간내에 정답이 가능하다. 핵심은 cost배열(메모이제이션) 에 최소비용을 계속 갱신해주고 이 최소비용보다 높다면 그 지점으로 이어지는 경로자체를 return시키는 것이다. #include #include #include int dr[4]={0,1,0,-1}; int dc[4]={1,0,-1,0}; int visited[30][30]={0,}; int cost[30][30]={0,}; u.. 2020. 9. 11. 이전 1 다음