본문 바로가기
반응형

BFS15

[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.
[leetcode] 126. Word Ladder II 문제 : https://leetcode.com/problems/word-ladder-ii/ 문자들 리스트인 wordList가 주어질 때, beginWord에서 한 글자씩만 바꿔서 wordList에 있는 문자열로 변환해가면서 endWord로 변환가능한 최소 변환횟수 문자열 변경 리스트들을 구하라. beginWord는 wordList에 없어도 되지만 endWord는 wordList에 있어야만 변경 가능한다. ex) // input beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] // output [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog.. 2021. 7. 25.
[Programmers] 가장 먼 노드 문제 : https://programmers.co.kr/learn/courses/30/lessons/49189 bfs로 풀 수 있다. bfs를 돌면서 현재 노드, 1번 노드와의 거리를 저장한다. 만약 노드와의 거리가 갱신되면 정답 변수를 0으로 갱신한다. 노드를 탐색할때 정답변수에 1을 더한다. 시간복잡도는 O(V + E). V = 정점개수, E = 간선개수 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/programmers/Graph/%EA%B0%80%EC%9E%A5%20%EB%A8%BC%20%EB%85%B8%EB%93%9C.cpp 2021. 6. 9.
반응형