# BFS
[프로그래머스 / Level3] 가장 먼 노드 (Java)
문제 보기 > BFS로 찾은 경로는 최단 경로이다. 풀이 그래프의 한 정점(1)에서 다른 정점들의 최단 거리를 구하기 위하여 BFS 사용 가장 먼 정점들의 수를 구하기 위하여 answer, maxPath 변수 사용 정점들의 거리를 계산하기 위하여 edges, paths, visited 를 사용 간선들의 정보인 edges 에 startVertex 가 ...
[BOJ] 1012 유기농 배추
https://www.acmicpc.net/problem/1012상하좌우 탐색https://velog.io/@ssoyeong/BOJ-2178-%EB%AF%B8%EB%A1%9C-%ED%83%90%EC%83%8922.05.05 위 문제 풀 때에 비해 해당
[자료구조] : BFS(너비 우선 탐색)
이번 시간에는 BFS(너비 우선 탐색)에 대한 내용이다.BFS(Breadth First Search, 너비 우선 탐색)DFS는 스택 자료구조를 활용해 구현했다면, BFS는 Queue를 활용한다.DFS는 갈 수 있는 곳까지 들어가서 확인하고, 갈 곳이 없으면 다시 되돌아
[ BOJ / Python ] 11060번 점프 점프
이번 문제는 BFS와 DP를 함께 사용하여 해결하였다. BFS로 현재 칸에서 점프할 수 있는 칸에 대한 정보를 담는다. 이때 dp리스트에 들어있는 값을 비교하여 현재 카운팅변수+1보다 다음 칸 dp값이 더 클 경우에만 다음칸에 대한 정보를 담게 된다. 이 과정에서 dp
[ BOJ / Python ] 3055번 탈출
이번 문제는 전에 풀었던 문제와 매우 유사하였다. 물의 좌표를 큐에 담고, 4방향으로 물을 퍼트리며 새로운 좌표를 새로운 큐에 넣은 후, 새로운 좌표들이 담긴 큐를 물의 좌표 큐로 복사시킨다. 이렇게 하면 불필요한 물의 좌표 탐색을 줄일 수 있다. 그리고 고슴도치의 이
DFS와 BFS
깊이 우선 탐색 (DFS, Depth-First Search): 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동참고 gif 파일스택 또는 재귀함수로 구현너비 우선 탐색 (BFS, Breadth-First Search): 최대한 넓게 이동한 다음,
[백준/c++] 17086번: 아기상어 2
문제 링크 - https://www.acmicpc.net/problem/170861단계 상어 배열일 입력받는다.2단계 입력받은 배열을 돌면서 상어가 있는지점에서 bfs를 시작한다.상어가 있는 지점마다 bfs를 돌면서 이전 dist값보다 더 작으면 더 작은값으로
백준 18404 현명한 나이트
문제링크실버 1그래프 탐색나이트의 최소 이동 수 구하기격자 판의 크기 N 상대편 말의 갯수 M나이트의 위치 X,YM줄의 상대편 말위치 A,B최소 이동 수 입력 순으로 출력최단 거리를 구하는 문제이므로 bfs를 사용해야한다. (물론 가중치가 1일경우 한정)bfs가 최단거
[ BOJ / Python ] 18405번 경쟁적 전염
이번 문제는 각 숫자의 위치를 deque로 저장한 리스트로 관리하고, BFS를 통해 주변을 탐색하며 0인 경우에 자신으로 숫자를 바꿔주는 방식을 사용하였다. 이때 각 숫자의 모든 위치를 계속해서 deque에 담으면 탐색의 크기가 커지기 때문에 새로 값을 입력한 값들만
백준 2644 촌수계산 JAVA
문제링크실버 2그래프 탐색 부모- 자식 => 1촌주어진 두사람의 촌수를 구하시오전체 사람의 수 n (사람이 1~n으로 주어짐)촌수를 계산해야하는 두사람의 번호부모 자식간의 관계 갯수 m부모 자식의 관계를 나타내는 번호 x,y(x가 y의 부모)촌수를 정수로 출력친척이 아
[ BOJ / Python ] 11559번 Puyo Puyo
이번 문제는 BFS를 통해 현재 위치와 연결된 위치에 자신과 같은 문자가 있는지를 찾고, 같은 문자가 4개 이상이 될 경우에만 방문처리 하도록 하였고, 4개보다 적을 때에는 다시 방문처리를 취소해주었다. 이렇게 해서 방문처리 리스트에 True로 표기되는 위치는 이번 차
[백준] 16953번 - A -> B
정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.2를 곱한다.1을 수의 가장 오른쪽에 추가한다. A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.첫째 줄에 A, B (1 ≤ A < B ≤ 10\*\*9)가 주어진다. A를 B로 바꾸는데
[BOJ] 17086 아기 상어 2
https://www.acmicpc.net/problem/17086아이디어처음에 1인 칸 저장하고 모든 0인 칸에 대해서 1인 칸까지의 거리를 구하려고 했는데 bfs로 풀어야 할 거 같아서 ? 위와 같이 구현하였다.1인 칸들을 queue에 모두 넣어주고, 상하
LV2. 거리두기 확인하기(2021 카카오 인턴십)
😁접근 방법첫 번째로 든 생각은 각각의 대기실을 기준으로 (0,0)부터 5X5크기의 행렬을 완전 탐색하며 P(면접자가 있는 곳) 를 만나게 되면P를 기준으로 거리가 1이라면 P가 있는지 1번에 해당이 안되면 거리가 2인지점을 탐색하여 파티션이 없는데 P인 지점이 있는