본문 바로가기

DFS3

[백준] 1520. 내리막길 문제 풀이 먼저 모든 경로의 수를 구해야하기 때문에 DFS를 사용해 경로를 구했다. 하지만 모든 경우의 수를 탐색하게 되는 경우 시간초과가 발생하기 때문에 이를 줄이기 위한 방법이 필요하다. 생각한 아이디어는 한 번 방문했던 좌표를 x,y라고 했을 때, (x,y) 에서 (N-1, N-1)까지의 경로는 이미 구해져있고 변하지 않기 때문에 다시 탐색할 필요가 없다는 점이다. 따라서 dfs를 진행하며 방문체크를 하고, 방문체크가 된 곳인 경우 저장되어 있는 경우의 수를 그대로 사용함으로써 시간을 줄일 수 있다. 하지만 주의할 점이 있다. 초기 작성한 코드는 다음과 같다. import java.io.BufferedReader; import java.io.IOException; import java.io.Inpu.. 2021. 4. 1.

[백준] 1967. 트리의 지름 문제 풀이 처음 시도했던 방법은 1번의 자식노드들을 시작점으로 잡아 DFS를 통해 탐색하면서 왼쪽 자식과의 거리, 오른쪽 자식과의 거리, 부모와의 거리 중에 상위 2개의 값을 골라 최대값을 갱신하는 방법으로 진행하였다. 그리고 그 최대값이 1번의 다른 줄기와 연결할 수 있는지(notCompleted), 아니면 이미 완성된 지름인지(completed) 판별하는 flag를 통해 최대 지름을 구하려고 했다. 이 방법이 잘못된 이유는 먼저 문제에서 이진 트리라는 조건이 없는데 이진트리라고 가정하고 풀었기 때문이고, 또한 위의 그래프에서 4-7 : 100 / 4-8 : 100으로 수정한 경우 왼쪽 줄기의 최대값이 200이 나와야하는데 4의 부모노드인 2가 자식이 하나밖에 없기 때문에 200 + 5로 갱신되는 문제.. 2021. 3. 6.

[백준] 1987. 알파벳 풀이 모든 경우의 수를 DFS로 탐색하며 이전에 방문한 알파벳인 경우 가지치기를 진행하엿다. 이 때 이전 방문 노드를 확인하는 방법으로 초기에는 ArrayList를 사용했지만 시간초과가 발생하였고 이에 대한 이유가 ArrayList의 remove 과정에서 O(N)의 시간복잡도가 발생했기 때문이라고 판단하였다. 그래서 이전 방문 알파벳을 유지하는 방식을 StringBuilder를 사용하였고 마지막 인덱스를 삭제함으로써 시간 초과를 해결하였다. 하지만 이 방법도 너무 느려서 이를 확인하는 방법으로 비트마스킹을 사용하였고 모든 경우에 distance를 비교하는 것이 아니라 유망하지 않은 경우에만 distance를 비교하도록 개선하였다. 비트마스킹으로는 현재 알파벳 - 'A'를 해줌으로써 포함 여부를 확인하였다.. 2021. 2. 19.

이전 1 다음

티스토리툴바