dfs21 [Leetcode] 1254. Number of Closed Islands 문제 : https://leetcode.com/problems/number-of-closed-islands/description/ 0(육지)과 1(물)로 이루어진 2차원 그리드가 주어집니다. 섬은 4방향으로 연결된 0으로 이루어진 최대 그룹이며, 폐쇄된 섬은 1로 둘러싸인 섬입니다. 폐쇄된 섬의 수를 반환하세요. 섬은 물로 완벽하게 둘러쌓여야 하므로 배열의 가장자리와 맞닿아 있는 육지는 섬으로 보지 않습니다. 따라서, 먼저 가장자리부터 탐색하면서 DFS 혹은 BFS로 가장자리 땅이 육지인 경우 연결된 육지들을 전부 물로 바꿔주는 사전작업을 해줍니다. 이 후, 땅들을 다시 탐색하면서 탐색 중인 땅이 육지인 경우 정답을 1 추가한 뒤, 마찬가지로 DFS/BFS로 연결된 육지들을 모두 물로 바꿔줘서 중복 정답.. 2023. 4. 6. [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. 이전 1 2 3 4 다음
