본문 바로가기

BFS18

[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] 785. Is Graph Bipartite? 문제 : https://leetcode.com/problems/is-graph-bipartite/ 인접한 노드의 색을 현재 노드의 색과 다른 색으로 칠해가면서 너비우선탐색을 진행한다. 칠할 수 있는 색은 두가지이다. 인접한 노드에 색이 칠해져 있지 않다면 현재 노드의 색과 다른 색으로 노드를 칠하고 칠한 노드를 탐색한다. 인접한 노드에 이미 색이 칠해져 있다면 현재 노드의 색과 비교한다 현재 노드의 색과 다른 색이면 유효한경우이다. 현재 노드의 색과 같은 색이면 유효하지 않으므로 false를 반환한다. 시작노드를 첫번째 노드만으로 잡고 너비우선탐색을 한 번만 진행한다면 [그림 1]과 같이 3~6번 노드의 유효성은 체크할 수 없다. 모든 노드를 시작지점으로 잡고 위 방법으로 노드들을 탐색하되 노드의 색 배.. 2022. 4. 29.
[Leetcode] 127. Word Ladder 문제 : https://leetcode.com/problems/word-ladder/ 문자들 리스트인 wordList가 주어질 때, beginWord에서 한 글자씩만 바꿔서 wordList에 있는 문자열로 변환해가면서 endWord로 변환가능한 최소 변환시퀀스 길이를 구하라. 만일 변환 불가능하다면 0을 반환하라. 126. Word Ladder2 와 비슷하게 풀었다. 126번과 이번문제와의 차이점은 반환값이 변환시퀀스 리스트인지, 변환시퀀스 길이인지이다. ex) // input beginWord = "hit", endWord = "cog", wordList = ["hit", "hot","dot","dog","lot","log","cog"] 126번 문제와 비슷하게 BFS로 풀고, 이를 위해 먼저 그래프 .. 2022. 2. 12.
[leetcode] 1293. Shortest Path in a Grid with Obstacles Elimination 문제 : https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/ m x n 정수 2차원 배열이 주어진다. 각 셸은 0(비어있음) 혹은 1(장애물) 이다. 최대 k개의 장애물을 제거할 수 있다고 할 때, (0, 0) -> (m-1, n-1)로 이동할 수 있는 최소 걸음 수를 구하라. 배열에서 1칸 이동을 1 걸음수로 본다. 상하좌우로 한 칸씩 이동할 수 있다. 불가능한 경우 -1을 반환하라. BFS로 풀었다. 탐색했는지 여부를 저장하기 위해 visits[x][y][k] 배열을 하나 만든다. visits[x][y][k] = 장애물 제거가능 횟수가 k번 남았을 때, grid[x][y]를 탐색한 적이 있는지 여부. BFS.. 2021. 9. 26.
[leetcode] 429. N-ary Tree Level Order Traversal 문제 : https://leetcode.com/problems/n-ary-tree-level-order-traversal/ 트리가 주어지면, 레벨 순서 순회 결과를 구하여라. 탐색문제. 너비우선탐색으로 구할 수 있다. 큐를 만들고 해당 큐에 루트 노드를 넣는다. 큐를 빌때까지 탐색하면서 새로운 큐에 탐색한 노드들의 자식 노드들을 넣는다. 큐가 빌때까지 탐색한 노드들이 같은 레벨에 있는 노드들이다. 새로운 큐를 만들었으면 해당 큐를 다시 빌때까지 탐색하면서 또다른 큐(다음 레벨의 노드들)를 만드는 과정을 반복한다. 시간복잡도는 O(N). N = 노드 개수. 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/429.%20N-ary.. 2021. 8. 7.
[programmers][2021카카오인턴십] 거리두기 확인하기 문제 : https://programmers.co.kr/learn/courses/30/lessons/81302 BFS로 풀었다. 하나의 대기실을 탐색하면서 people 좌표를 찾으면 BFS를 돌린다. 탐색하면서 테이블을 만나면 계속 탐색, 파티션을 만나면 탐색 중지, 또다른 people을 만나면 거리두기 실패임을 알 수 있다. 만일 탐색하면서 3이상의 거리가 된다면 거리두기를 성공적으로 하고 있으므로 BFS 탐색을 중지해도 된다. 시간복잡도는 하나의 people 좌표에서 BFS를 돌리는데 people 좌표 탐색 O(NM). 한 번의 BFS 탐색시 O(NM)이 소요되므로 총 O((NM)^2). 하지만 거리두기 2 이상은 탐색할 필요가 없으므로 BFS 탐색 시간복잡도는 상하좌우 4방향으로 2번만 탐색하면 되.. 2021. 7. 30.

티스토리툴바