BFS6 [코딩테스트 대비] 너비 우선 탐색 (BFS) 정리 BFS (너비 우선 검색) 정리 소개 Root Node 혹은 다른 임의의 노드에서 인접한 노드를 먼저 탐색하는 방법이다. Queue를 사용해서 구현한다. 시간 복잡도 인접 리스트 : O(V + E) 인접 행렬 : O(V^2) 접점(V), 간선(E) class Graph { private int V; private LinkedList adj[]; Graph(int v) { V = v; adj = new LinkedList[v]; for (int i=0; i 2019. 3. 30. [Java]백준 7569번 :: 토마토 백준 온라인 저지 7569번 - 토마토 Java 알고리즘 문제풀이 풀이 BFS(너비 우선 탐색) 문제입니다. BFS를 이용해 해결하는 문제는 3가지 조건을 가지고 있다. 1. 최소 비용 문제 2. 간선의 가중치가 1이다. 3. 정점과 간선의 개수가 적다. (시간제한, 메모리 제한 내에 만족한다.) DFS, BFS 관련 자료 : https://developer-mac.tistory.com/64 토마토 문제에서는 BFS를 이용하면 된다. 익은 토마토를 큐에 담아 좌, 우, 위, 아래 총 4가지 경로를 탐색해주면된다. 이때 익은 토마토 기준으로 다른 칸으로 갈때 (안익은 토마토 0이 있을 때만, 비어 있는 공간 -1일 때는 제외한다.) 그리고 3차원 배열을 사용했기 때문에 이전 토마토 문제보다 신경써줘야 할 .. 2019. 3. 12. [Java]백준 7576번 :: 토마토 백준 온라인 저지 7576번 - 토마토 Java 알고리즘 문제풀이 풀이 BFS(너비 우선 탐색) 문제입니다. BFS를 이용해 해결하는 문제는 3가지 조건을 가지고 있다. 1. 최소 비용 문제 2. 간선의 가중치가 1이다. 3. 정점과 간선의 개수가 적다. (시간제한, 메모리 제한 내에 만족한다.) DFS, BFS 관련 자료 : https://developer-mac.tistory.com/64 토마토 문제에서는 BFS를 이용하면 된다. 익은 토마토를 큐에 담아 좌, 우, 위, 아래 총 4가지 경로를 탐색해주면된다. 이때 익은 토마토 기준으로 다른 칸으로 갈때 (안익은 토마토 0이 있을 때만, 비어 있는 공간 -1일 때는 제외한다.) 이전 값에서 +1을 해주면서 전체를 탐색하면 된다. import java... 2019. 3. 12. [코딩테스트 대비] DFS, BFS 정리 DFS, BFS 정리 DFS, BFS는 그래프에 속하는 알고리즘이다. 코딩테스트에서 경로를 찾는 문제에서 많이 출제가 된다. DFSRoot Node 혹은 다른 임의의 Node에서 다음 분기(Branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.Stack 혹은 재귀함수(Recursion)으로 구현된다.경로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게되면 다른 방향으로 다시 탐색을 진행모든 노드를 방문하는 경우에 이 방법을 사용한다.시간 복잡도인접 리스트 : O(V + E)인접 행렬 : O(V^2)접점(V), 간선(E) Java Code1234567891011121314151617181920212223242526272829303132333435363738/*.. 2019. 3. 11. [Java]백준 4963번 :: 섬의 개수 백준 온라인 저지 4963번 - 섬의 개수 Java 알고리즘 문제풀이 코딩테스트 DFS, BFS : https://developer-mac.tistory.com/64 풀이 그래프를 이용한 경로탐색 알고리즘에 대표적으로 2가지가 존재한다. DFS (깊이 우선 탐색) BFS (너비 우선 탐색) 코딩테스트에서 대표적으로 출제되는 문제라 알아두는 것이 좋은 알고리즘인데, 이 문제는 이 두가지 알고리즘을 연습하기에 좋은 문제이다. 실제 코딩테스트에서는 경로를 찾는 문제에서 많이 쓰인다. DFS 알고리즘에 경우 두 가지 방법으로 풀 수 있는데, 첫 번째로 스택을 이용하는 것 두 번째로 재귀함수를 이용하는 것인데, 재귀함수를 이용하는 것이 가장 보편적이고 짧은 코드를 작성할 수 있다. BFS 알고리즘은 Queue를 .. 2019. 3. 11. [Java]백준 1260번 :: DFS와 BFS 백준 온라인 저지 1260번 - DFS와 BFS Java 알고리즘 문제풀이 풀이 그래프를 이용한 경로탐색 알고리즘에 대표적으로 2가지가 존재한다. DFS (깊이 우선 탐색) BFS (너비 우선 탐색) 코딩테스트에서 대표적으로 출제되는 문제라 알아두는 것이 좋은 알고리즘인데, 이 문제는 이 두가지 알고리즘을 연습하기에 좋은 문제이다. 실제 코딩테스트에서는 경로를 찾는 문제에서 많이 쓰인다. DFS 알고리즘에 경우 두 가지 방법으로 풀 수 있는데, 첫 번째로 스택을 이용하는 것 두 번째로 재귀함수를 이용하는 것인데, 재귀함수를 이용하는 것이 가장 보편적이고 짧은 코드를 작성할 수 있다. BFS 알고리즘은 Queue를 사용해서 문제를 해결하면 된다. import java.util.*; public class .. 2019. 3. 7. 이전 1 다음