반응형 Programming/Algorithm29 백준 7576 토마토 알고리즘 문제 자바 JAVA CODE 백준 7576 토마토 문제는 토마토가 들어있는 1의 칸에서 시작해서 전체 토마토가 익어가는 기간을 구하는 문제다. 복잡해보이지만 결국 BFS 알고리즘으로 해결할 수 있는 문제다. 첫번째 노드에서 상하좌우로 접하고 있는 노드를 찾아서 counter를 통해 1씩 증가해가면서 마지막 노드까지 가는 최단거리를 구하는 문제와 일맥상통하다. DFS + BFS 알고리즘 이해하기 백준 1012 유기농 배추 알고리즘 자바 JAVA 백준 1012 유기농 배추 알고리즘 자바 JAVA 문제 백준 1012 유기농 배추 문제는 DFS/BFS 알고리즘을 사용해서 풀어보는 문제다. 기존 문제와 다른 점은 주어진 배열이 정사각형이 아닌 직사각형이라는 incomeplus.tistory.com 백준 2178 미로 탐색 알고리즘 자바 JA.. 2022. 3. 11. 백준 1012 유기농 배추 알고리즘 자바 JAVA 백준 1012 유기농 배추 알고리즘 자바 JAVA 문제 백준 1012 유기농 배추 문제는 DFS/BFS 알고리즘을 사용해서 풀어보는 문제다. 기존 문제와 다른 점은 주어진 배열이 정사각형이 아닌 직사각형이라는 점이다. 두개의 알고리즘으로 푸는게 정석이기 때문에 두개 방법 모두 적용해서 결과값을 비교해보기로 한다. 문제의 시간 제한은 1초, 메모리 제한은 512MB가 주어진다. DFS/BFS 알고리즘 참고 백준 2667 자바 JAVA 단지 번호 붙이기 알고리즘 백준 2667 단지번호붙이기 문제는 DFS/BFS 하위 문제다. 0과 1로 구성된 맵에서 1인 지점을 찾아서 군집의 갯수와 군집내 요소들의 갯수를 파악하는 문제다. 풀이는 스택+재귀함수를 이용한 DFS와 큐 incomeplus.tistory.com .. 2022. 3. 8. 백준 2178 미로 탐색 알고리즘 자바 JAVA 풀이 백준 2178 미로 탐색 BFS 알고리즘 JAVA 자바 백준 2178 미로 탐색 알고리즘은 완전탐색인 BFS 알고리즘으로 풀어야 하는 문제다. 상하좌우로 움직일 수 있고, 입력단에서 주어지는 N,M 좌표까지 가장 최단거리로 움직이는 수를 구하는 문제다. 최초 시작점인 (0,0) 좌표와 마지막 도착위치도 카운팅에 포함한다. 대표적인 탐색알고리즘은 DFS와 BFS를 동시에 살펴본다. DFS는 루트노드에서 단말노드까지 한번에 진입하여 탐색하는 스택 기반 알고리즘이다. 즉 최단거리를 구하는 알고리즘으로 적합하지 않다. DFS로 탐색을 시도하면 가능한 모든 경로를 탐색하기 때문에 최단거리가 나오지 않는다. BFS 알고리즘을 사용해서 문제를 풀기 위해서는 탐색된 노드의 순서를 기록하는 2차 배열이 필요하다. 완전탐.. 2022. 3. 8. 백준 2667 자바 JAVA 단지 번호 붙이기 알고리즘 백준 2667 단지번호붙이기 문제는 DFS/BFS 하위 문제다. 0과 1로 구성된 맵에서 1인 지점을 찾아서 군집의 갯수와 군집내 요소들의 갯수를 파악하는 문제다. 풀이는 스택+재귀함수를 이용한 DFS와 큐를 이용한 BFS로 풀어볼 수 있다. DFS와 BFS 알고리즘을 먼저 이해해야 풀 수 있는 문제다. 백준 1260 DFS와 BFS 알고리즘 자바 JAVA 백준 1260번 문제는 DFS(깊이우선탐색)과 BFS(넓이우선탐색) 알고리즘을 이해하는 문제다. 비선형 자료구조인 트리구조에서 탐색을 하기 위해서는 노드(node)와 브랜치(branch)를 이동하면서 각각의 incomeplus.tistory.com DFS 알고리즘 먼저 스택과 재귀함수를 이용한 DFS를 통한 방법은 2개의 순회과정을 거친다. 첫번째 순.. 2022. 3. 7. 백준 2606 바이러스 자바 JAVA DFS BFS 알고리즘 리뷰 백준 2606 문제는 DFS와 BFS 중 하나를 사용해서 웜 바이러스가 걸린 컴퓨터의 댓수를 구하는 문제다. 시작점은 노드 1에서 부터 출발한다. 주어진 노드의 갯수(컴퓨터의 댓수)N과 브랜치(컴퓨터간 연결된 네트워크 갯수)M이 주어지고, 이 후 브랜치의 연결 지점을 입력받게 된다. DFS는 깊이우선탐색 알고리즘으로 주어진 노드에서 가장 깊은 단말노드까지 탐색을 진행하고, 다음 노드로 이어지는 알고리즘이다. BFS는 너비우선탐색으로 동일한 깊이의 노드들을 모두 탐색하고 다음 깊이 단계로 넘어가는 알고리즘이다. 백준 2606 문제는 DFS와 BFS에 대한 개념이 있어야 한다. DFS/BFS 기본 문제 리뷰 백준 1260 DFS와 BFS 알고리즘 자바 JAVA 백준 1260번 문제는 DFS(깊이우선탐색)과 .. 2022. 3. 3. 백준 1260 DFS와 BFS 알고리즘 자바 JAVA 백준 1260번 문제는 DFS(깊이우선탐색)과 BFS(넓이우선탐색) 알고리즘을 이해하는 문제다. 비선형 자료구조인 트리구조에서 탐색을 하기 위해서는 노드(node)와 브랜치(branch)를 이동하면서 각각의 노드값을 기록해야 한다. DFS(Depth First Search, 깊이우선탐색) 깊이우선 탐색은 노드의 깊이가 깊은 순서를 먼저 탐색하는 알고리즘이다. 노드의 시작은 1부터 시작하고, 가장 깊은 곳의 노드까지 방문을 마치면 다음 자식노드로 이동해서 노드의 끝가지 이동하게 된다. DFS 알고리즘은 인접행렬 자료구조와 재귀 알고리즘을 사용해서 구현 가능하다. DFS를 구현하기 위해 사용되는 인접행렬은 대칭행렬의 모습을 가지고 있다. 백준 1260번에서 처음 입력값을 유한 그래프로 표시하면 아래와 같다... 2022. 3. 3. 이전 1 2 3 4 5 다음 반응형
