Remember Your Place

1. 문제 링크https://www.acmicpc.net/problem/92022. 문제 풀이 생각보다 플래티넘 V 정도의 문제들은 정석적인 풀이가 아닌 다른 방식으로도 풀리는 경우가 있는 것 같습니다. 이번 문제도 [BOJ] 14942 개미 문제와 같이 DFS로 풀렸습니다. 입력으로 단어들이 300,000 미만 정도의 개수로 주어지는데, 솔직히 시간제한과 메모리 제한이 각각 10초와 512 MB로 매우 널널합니다. 저는 트라이(Trie)와 DFS를 사용한 풀이보다는 Set을 활용한 DFS를 채택하였습니다. HashSet에 모든 단어를 저장한 후, DFS를 통해 단어의 존재 여부를 확인하며 문제를 해결했습니다. 이렇게 구현한 이유는 HashSet의 탐색 속도가 평균적으로 O(1)에 가깝고, 단어 길이가 ..

1. 문제 링크https://www.acmicpc.net/problem/149422. 문제 풀이 이 문제에서는 방의 개수 최댓값이 100,000으로 주어집니다. 보통 input 값으로 10만 이상의 단위가 나오게 된다면 단순 구현으로는 못 푸는 경우가 많죠. 그래서 원래라면 희소 배열(Sparse Table)이라는 개념을 적용해서 풀어야 하는 문제이긴 합니다만. 이 문제는 단순 DFS로 풀립니다! 물론 아직 푼 사람이 그렇게 많은 편이 아닌 데다가 추가 테스트 케이스가 있어야 플래티넘다운 문제라고 할 수 있겠는데 ..   static void dfs(int node, int parentNode) { parent[node] = parentNode; for (Edge edge : g..