DFS 썸네일형 리스트형 백준 1520 내리막 길 오늘도 DP 문제이다. 2차원 지도를 입력으로 받아 0, 0 위치에서 N - 1, M - 1 위치까지 경로가 몇개 있는지 찾는 문제이다. DP 없이 그냥 문제 푼다고 생각하면 DFS를 써서 탐색을 돌려버릴 것 같다. 하지만 맵 크기가 작은 편이 아니라 그렇게 돌리면 Timeout이 발생할 가능성이 크다. 처음에 DP 접근을 dp[i][j] = 0, 0에서부터 i, j 까지 경로의 수 라고 생각을 해봤는데 생각을 아무리 해봐도 잘 답이 나오지 않았다. 그러고 한번 뒤집어 접근을해봤다. dp[i][j] = i, j 에서부터 N-1, M-1 까지 경로의 수로 생각을 하고 접근을 했다. 이 방향이 더 좋았던 것 같다. 그리고, dp 배열을 채우는 과정은 DFS로 흘러가게 된다. 현재 픽셀에서, 다음 픽셀을 찾고.. 더보기 백준 1987 알파벳 DFS로 탐색하는 문제이다. 일단 쭈우욱 탐색을 하는 중에는, 이미 지나온 알파벳이 중복으로 나타날 수 없다. 가장 길게 이을 수 있는 칸 수를 구하면 된다. DFS함수는 상하좌우 픽셀의 탐색가능여부를 확인 후, 다른 픽셀로 넘어가기 전에 현재 알파벳 방문을 표시한다. 이 과정이 없으면, 다음 픽셀을 탐색할때 중복되는 알파벳을 포함하므로 끝도없이 이어지게 된다.("ABBDSAAAAADDAAAAA..." 같이) 원래 Visit 배열이 아닌, 상태를 나타내는 구조체에 string으로 지금까지 방문한 문자열을 저장하고, 마지막 탐색이 막히면 그 때 string의 길이를 리턴하는 방식으로 작성했는데, 매 번 string에서 find를 해야 하고 어차피 알파벳은 개수가 정해져 있으니 배열을 만들어 인덱스로 접근하.. 더보기 백준 3109 빵집 원웅이의 범죄행위를 도와주어야 하는 문제이다. 가장 왼쪽 열에서 가장 오른쪽 열까지 우상, 우, 우하로 움직이며 경로가 몇개가 되는지 구하는 문제이다. 각 경로는 서로 겹쳐서는 안된다. 경로를 찾을때는 DFS로 탐색을 한다. 현재 픽셀에서 우상, 우, 우하로 탐색하면서 재귀로 호출한다. - 우상, 우, 우하 탐색을 했을 때 전부 true가 없으면 false를 최종적으로 리턴하게 된다. 만약 현재 픽셀이 가장 오른쪽 열이라면, true를 리턴한다. DFS를 짤 때, 재귀로 일단 생각하게 되는데 앞으로 풀어볼 때는 재귀가 아닌 코드로 한번 작성해보아야겠다. 재귀로 짤 경우 디버그가... 너무... 힘들다... Visit[][] 배열은 Map 크기와 동일하게 만들어서 각 픽셀을 방문할때마다 true로 만든다... 더보기 백준 1167 트리의 지름 트리를 받아. 트리에서 나올 수 있는 가장 긴 거리(트리의 지름)를 구하는 문제이다. 원래 구현은 각 노드에서 DFS를 해 그 중에서 가장 긴 값을 구하는 코드를 작성했다. 우왕 탐색코드만 짜고 돌기만 하면 되네! 했는데 당연하게도 타임아웃이 떴다. 가장 긴 길이를 더 빠르게 구할 방법이 없을까 했는데 질문들을 보니 2번이면 계산이 가능하다고 한다. 머리로 여러번 생각해봤는데, 도저히 답이 안나와서 한걸음 떨어져서 생각해보니 그래프와 트리를 막 섞어서 생각하고 있었다. 트리의 경우, 무조건 어느 노드는 말단이 있다. 일단 아무 노드에서 가장 먼 노드를 구하고, 거기서부터 가장 먼 거리를 구하면 그게 바로 트리에서 나올 수 있는 가장 긴 거리이다. 그러면 2번만에 된다는 말이 맞다. 첫번째는 가장 멀리 있.. 더보기 이전 1 다음
