본문 바로가기

BFS17

[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.
[leetcode] 542. 01 Matrix 문제 : https://leetcode.com/problems/01-matrix/ 0과 1로 이루어진 mat 배열이 주어질 때, 각 셸에서 0과 가장 가까운 거리를 저장한 배열을 만들어 반환하라. BFS로 풀었다. 배열을 탐색하면서 0인 셸들의 x, y 좌표를 큐에 넣는다. 큐에 넣은 셸들의 0과 가장 가까운 거리는 0이다. 두 번 탐색하면 안되기 때문에 visit 배열을 만들고 큐에 넣은 좌표들의 visit을 true로 세팅한다. 큐를 탐색하며 큐의 front에 있는 좌표(let, (x, y))의 상하좌우 셸들 중에 탐색하지 않은 좌표(let, (nx, ny))들을 큐에 넣는다. 그리고 큐에 넣은 좌표들의 탐색여부를 true로 갱신, 정답 배열의 값을 (x, y) 정답 배열의 값 + 1로 갱신한다. m.. 2021. 7. 29.