Min IT's Devlog

풀이 일자: 23.06.01 난이도: [Medium] 분류: [BFS] 문제 내용 내용은 0과 1로 이루어진 배열이 주어졌을 때 (0,0)에서 (n-1,n-1)로 0만 밟으면서 이동할 때 최단 거리를 리턴하는 문제로 이동할 수 있는 범위는 edge와 맞닿아있는 총 8개의 면에 갈 수 있다. 문제 해결 흐름 1. 항상 이러한 배열과 최단거리의 조합은 BFS와 DFS 둘 중 하나를 떠올릴 수 있다. → 나는 BFS를 순회 알고리즘에서 매우 선호하기도 하고 DFS를 사용하기에는 BFS를 사용하는 것보다는 최단거리를 계산하기 부적합하다고 생각하여 BFS를 이용하여 문제를 해결했다. class Solution: def shortestPathBinaryMatrix(self, grid: List[List[int]])..

풀이 일자: 23.05.19 난이도: [Medium] 분류: [DFS, BFS, Union Find, Graph] 문제 내용 이번 문제는 undirected graph가 주어졌을 때 이 노드들을 A와 B그룹으로 나눌 수 있는지 여부를 리턴하는 문제로 각 A,B 내부의 노드끼리는 연결되어 있지 않아야 한다. A와 B는 연결되어 있어도 상관없다. 문제 해결 흐름 1. 처음에는 Graph문제이고 A와 B그룹으로 나눌 수 있기 때문에 Union-Find를 떠올렸다. → 가능은 하겠지만 좀더 쉬운 방법을 떠올리고자 했다 2. A그룹과 B그룹을 나누고 같은 그룹의 노드들이 서로 인접하면 안되기 때문에 노드를 색칠하는 문제로 생각해도 되겠다는 생각을 할 수 있다. → BFS를 이용하여 각 level별로 같은 색으로 ..

풀이 일자: 23.04.06 난이도: [Medium] 분류: [Array, DFS, BFS, Union Find] 문제 내용 문제의 내용은 0(land), 1(water)로 이루어진 배열이 주어졌을 때 사면이 물로 둘러싸여있는 섬의 수를 구하는 문제였다. 문제 해결 흐름 1. 일단 가장 먼저 떠오른 방법은 Union-Find이긴 했다. → 1의 group과 0의 group으로 나눠질거고 0내부에서도 각 섬별로 grouping이 되는거니까 Union-Find로도 가능하다. 2. Union-Find는 간단하지만 더 쉬운 방법을 찾아볼 필요가 있다. DP나 DFS정도를 생각할 수 있겠다. → DP는 점화식을 뽑아야 하는데 그것보다는 더 쉬운 방법일 수 있는 DFS를 선택하자. 3. 우선 edge에 0이 등장한..