본문 바로가기

dfs20

[Leetcode] 980. Unique Paths III 문제 : https://leetcode.com/problems/unique-paths-iii/ m x n 정수형 배열 grid가 주어진다. 1 : 시작 지점. (1개 존재) 2 : 종료 지점. (1개 존재) 0 : 걸을 수 있는 곳 -1 : 장애물 상하좌우 4방향으로 이동가능할 때, 시작지점에서 종료지점으로 갈 수 있는 방법의 수를 구하라. 백트래킹. 시작지점부터 장애물이 아닌 곳으로 이동하면서 이동횟수를 저장하면서 상하좌우 방향으로 탐색한다. 탐색하면서 지나간 자리는 다시 못 지나가게 별도의 플래그 배열에 탐색한 위치는 표시를 해둔다. 종료지점에 도달했을 때, 걸음의 수가 grid 배열의 0, 2 cell의 수와 같다면 정답이 가능하므로 정답 방법의 수에 1을 더한다. 시간복잡도는..? 소스코드 : h.. 2021. 11. 2.
[Leetcode] 130. Surrounded Regions 문제 : https://leetcode.com/problems/surrounded-regions/ 'X', 'O' 로 이루어진 m x n 배열이 있다. 'O'로 둘러쌓인 'X' 구역이 있다면 이들을 모두 'O'로 바꾸어라. DFS, BFS 탐색으로 X로 이루어진 구역들을 구할 수 있다. 이 때, m x n 배열의 경계선에서부터 시작하는 X 구역들은 O로 둘러쌓인게 아니므로 범위에서 제외되어야 한다. 따라서 먼저 경계선에 존재하는 X 구역들을 모두 DFS나 BFS 탐색으로 이미 방문했다고 갱신한다. 이 후, 배열을 탐색하며 이미 방문/탐색 하지 않은 X구역들을 구한 뒤 이들을 모두 O로 바꿔주면 정답이 된다. 시간복잡도는 O(nm) 소스코드 : https://github.com/fpdjsns/Algorit.. 2021. 11. 1.
[Programmers] 타겟 넘버 문제 : https://programmers.co.kr/learn/courses/30/lessons/43165 DFS 방식으로 탐색하면서 모든 인덱스의 숫자들을 더하거나 빼는 경우의 합을 구한다. 모든 numbers 를 탐색했을 때 합이 targetSum과 같다면 정답 +1을 해준다. 시간복잡도는 하나의 인덱스에 더하거나 빼는 경우, 두 번을 탐색하므로 O(2^N). N = |numbers| 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/programmers/%ED%83%80%EA%B2%9F%20%EB%84%98%EB%B2%84.cpp 2021. 8. 5.
[leetcode] 827. Making A Large Island 문제 : https://leetcode.com/problems/making-a-large-island/ n x n 크기의 0과 1로 이루어진 grid 배열이 입력으로 주어질 때, 1로 이루어진 섬의 최대 크기를 구하여라. 이 때, 최대 한 번 0을 1로 바꿀 수 있다. dfs를 한 번 돌리면서 연결된 1들을 하나의 섬으로 보고 섬의 번호와 해당 섬의 크기를 map에 저장한다. grid 배열을 한 번 더 탐색하면서 탐색하는 셸이 0인 경우 해당 셸의 상하좌우에 있는 섬의 번호들을 가져온다. 상하좌우에 있는 섬들의 합 + 1 (탐색중인 0 셸이 1로 바뀌면서 증가된 섬의크기)들이 하나의 0을 1로 바꿨을 때 구할 수 있는 섬의 크기이다. 구할 수 있는 섬들의 크기들 중 최대값이 정답이 된다. 시간/공간 복잡.. 2021. 8. 2.
[programmers][월간 코드 챌린지 시즌2] 모두 0으로 만들기 문제 : programmers.co.kr/learn/courses/30/lessons/76503# 연결된 두 점의 한 쪽은 +1, 다른 한 쪽은 -1을 하면 플마제로이기 때문에 결국 모든 노드의 가중치들의 합은 유지된다. 따라서 모든 노드들의 가중치 합이 0가 되지 않는다면 -1을 반환한다. 모든 노드들의 가중치 합이 0이 아니라면 가중치를 0으로 만드는 것은 가능하다. 임의의 노드를 루트노드라 가정하고 해당 노드로 다른 모든 노드들의 가중치를 루트노드로 이동시켜보자. [그림 1]은 가중치 0을 가진 노드를 루트노드라 가정하여 다른 노드들의 가중치를 순수하게 옮긴다고 가정했을 때의 이동횟수이다. 예를 들어 3 노드의 가중치를 0 노드로 옮길 때 -1 노드를 거치지만 단순히 거쳐가는 노드로만 사용된다. 총.. 2021. 4. 17.
[leetcode][329] Longest Increasing Path in a Matrix 문제 : leetcode.com/problems/longest-increasing-path-in-a-matrix/ N*M 정수 배열이 주어질 때, 각 셸에서 상하좌우에 위치한 셸이며 현재 셸의 수보다 높은 수를 가지는 셸로 이동가능하다. 가장 긴 경로 길이를 구하라. DFS + DP 로 풀었다. i번째 셀에서 상하좌우로 이동가능한 곳으로 이동하면서 이동 가능한 경로의 최장 길이를 저장하는 배열(let, dp)을 만든다. dp[i] = min(dp[상하좌우 중 이동가능한 곳]) 위 점화식을 적용하며 dp배열을 dfs로 탐색하면서 세팅한다. dp 배열이 이미 갱신된적 있다면 새로 값을 구하지 않고 해당 값을 사용하여 시간을 줄일 수 있다. 시간복잡도, 공간복잡도 모두 O(NM). 소스코드 : github.c.. 2021. 3. 4.