본문 바로가기

BFS18

[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.
[leetcode][310] Minimum Height Trees 문제 : leetcode.com/problems/minimum-height-trees/ N개의 노드가 있고 N-1개의 간선으로 연결된 무방향 그래프가 주어진다. 그래프는 순환 경로가 없고 모든 노드가 연결되어 있다. 노드들 중 루트 노드가 된다면 최소 높이를 가진 트리를 가질 수 있는 노드들을 구하라. 지난번에 푼 트리지름 관련 문제 참고. 임의의 지점 0 노드를 시작점으로 BFS를 한 번 돌려서 가장 멀리 있는 노드들을 가져온다. 이 노드들로 다시 한 번 BFS를 돌려서 가장 멀리있는 노드들을 가져오면 트리의 지름을 가지는 2개의 노드(let, a, b)를 알 수 있다 BFS를 만들면서 이전에 방문한 노드 번호를 저장하고 a -> b (트리 지름) 경로를 지날 때 방문하는 노드들을 임의의 배열에 저장한.. 2020. 11. 6.
[BOJ][1346] 구슬 탈출 2 문제 : www.acmicpc.net/problem/13460 너비 우선 탐색(BFS)를 이용한다. 방문 여부는 빨간 공 (x, y) 파란 공 (x, y) 이용해서 4차원 배열을 만들어서 체크한다.(check 배열) 큐 안에는 (빨간 공(x, y), 파란 공(x, y), 기울인 횟수)를 저장한다. 벽 또는 탈출구가 나올 때까지 한 방향으로 공을 계속 움직인다. 파란 공이 빠져나오는 경우는 불가능한 경우이고 빨간 공만 나온 경우는 기울인 횟수를 출력하고 종료한다. 파란 공과 빨간 공이 겹치는 경우, 기울이기 전 위치를 비교해서 겹치지 않게 해준다. 만약, 아래 방향으로 움직이는 경우 기울이기 전 빨간 공이 파란 공보다 아래에 있었다면 파란 공의 위치를 1위로 옮긴다. 공들의 위치를 겹치지 않게 조정한 다음.. 2020. 11. 1.
[BOJ][16236] 아기 상어 문제 : www.acmicpc.net/problem/16236 거리가 가장 가까운 먹을 수 있는 물고기를 찾되 조건에 해당하는 물고기가 여러마리라면 가장 위, 가장 왼쪽에 있는 물고기를 먹으러 간다. 가장 가까운 먹을 수 있는 물고기를 찾아야하므로 BFS(너비우선탐색)을 하는데 가장 위, 가장 왼쪽에 있는 물고기를 찾아야 하므로 큐가 아닌 우선 순위 큐를 사용했다. 우선 순위 큐에 (현재 상어 위치와 이동하고자 하는 좌표간 거리(dist), (이동하고자 하는 좌표(x, y))) 를 저장한다. 해당 큐에서 좌표간 거리가 가장 짧고, 이동하고자 하는 좌표(x, y)를 x가 작을 수록, y가 작을수록 높은 우선순위를 가진다. 우선 순위 : dist 오름차순 -> x 오름차순 -> y 오름차순 상어가 지나갈 수.. 2020. 10. 31.

티스토리툴바