dfs2 불량 사용자 [2019 카카오 겨울 인턴쉽] C++ DFS Set 을 이용한 풀이 처음엔 단순히 for문으로 완전탐색을 하면 풀릴 줄 알았다. 하지만 생각해보니 user_id와 banned_id의 개수는 총 8개 이하이므로 다중 for문으로는 전체 개수를 구할 수 없었다. 따라서 브루트 포스방식으로 풀려면 DFS를 적용해야했다. 2번 테스트케이스의 예로 들면 user_id의 인덱스는 0부터 4까지이고 banned_id의 인덱스는 0부터 2까지이다. 따라서 user_id의 인덱스 banned_id의 인덱스 012 0 1 2 013 0 1 2 014 0 1 2 023 0 1 2 024 0 1 2 034 0 1 2 021 0 1 2 023 0 1 2 ... 102 0 1 2 103 0 1 2 이런식으로 서로 같은 문자열인지 체크한다. *를 빼고 같은 문자열인지 포문을 돌며 한글자씩 체크한다.. 2020. 9. 12. 경주로 건설 - 카카오 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 다음
