'백준1890' 태그의 글 목록

[알고리즘] 백준 1890번 문제 https://www.acmicpc.net/problem/1890 풀이 오늘도 역시 BFS/DFS 문제를 풀어보았습니다. 이 문제를 처음 봤을 때 여타 다른 문제와 다를 것이 없다고 생각했고 BFS를 이용해서 풀면 쉽게 풀릴 것이라고 생각했습니다. 그리고 BFS로 코드를 작성하고 실행시켜보니 역시 원하는 출력 결과물이 나왔습니다. 하지만 사이트에 제출하니 시간 초과라는 문구가 떴습니다. 그제서야 깨달았죠! 단순히 BFS/DFS로 풀면 안되겠구나! N이 100이 된다면 상당히 많은 칸을 점프할 것이고 그 중 중복 탐색이 생길 수 있다는 것을 알게되었습니다. 그렇기 때문에 BFS/DFS와 DP를 같이 사용해야하는 다소 복잡한 문제였습니다. 다음은 저의 풀이 과정입니다. 처음..

Algorithm 2018. 1. 31. 12:41

이전 1 다음