이전 글(https://begintoend.tistory.com/49)에서 이어진다. 문제를 다시 생각해봤을 때 Queue가 우선순위 큐라는 것을 염두해 두고, 큐가 빌 때 까지 while문을 도는 걸 생략하고 작성한거 같다. 재귀로 구현하기 위해 함수를 따로 빼서 구현하였다. package baekjoon; import java.util.PriorityQueue; import java.util.Scanner; class Cabbage { int x; int y; public Cabbage(int x, int y) { this.x = x; this.y = y; } public int getX() { return x; } public int getY() { return y; } } public class ..

문제 링크 : https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 처음에는 M*N 만큼 for문을 돌아서 상하좌우 인덱스로 1을 찾은 후에 카운트 하는 단순한 문제로 생각했었는데, 예상 외로 여러가지 따질 문제 였던 거 같다. 처음에 짰던 코드를 써보자면 다음과 같다. package baekjoon; import java.util.Scanner; public class OrganicCabbage_1012 { public static int findCabbage..

[ 문제] 공항에는 G개의 탑승구가 있으면 각각은 1부터 G까지의 번호로 구분이 된다. 공항에는 P개의 비행기가 차례대로 도킹할 예정이며, i번째 비행기를 1번부터 gi(1

[정의] 가장 짧은 경로를 찾는 알고리즘 - 다익스트라 알고리즘 특정한 노드에 출발하여 다른 모든 노드로 가는 최단 경로 계산 그리디 알고리즘으로 분류 (매 상황에 가장 적은 노드 선택) 시간 복잡도 O(N^2) -> 우선순위 큐 사용 O(NlogN) 줄임. 힙 연산. 원소를 모두 우선순위 큐에 넣었다가 모두 빼내는 연산과 유사. (ElogV : E는 간선, V는 노드) 방법 1. 출발노드 설정 2. 최단 거리 테이블 초기화 3. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택 4. 해당 노드를 거쳐 다른 노드로 가는 비용 계산 -> 최단 거리 테이블 갱신 5. 3-4번 반복 : 매 단계마다 노드를 순차적으로 탐색 - boolean visited[] : 노드 방문 true/fal..

DFS - 깊이 우선 탐색(Depth-First Search). 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘. - 스택(혹은 재귀함수) 이용 먼저 재귀적으로 구현한 DFS는 다음과 같다. package codingTest; public class DFS { static void dfsGraph(int graph[][], int num, boolean visited[]) { // num 노드를 방문 처리 visited[num] = true; // 방문한 노드 프린트 System.out.println(num); // 이중배열에서 graph[num]의 길이만큼 for문을 돌림. for(int i=0; i

DFS : 깊이 우선 탐색으로 자식의 자식을 끝까지 탐색한 후 다시 돌아오는 방식. 기본적으로 정점과 간선의 개념을 알아야 한다. - 정점 : 노드(?) 비슷한 개념 - 간선 : 정점과 정점을 이으는 선. Java 코드로 구현하면 다음과 같다. package practice; class dfsGraph { int num; // 2차원 배열로 간선 표현. 0/1 이면 정점을 연결하는 간선 없음/있음. int graph[][]; boolean visited[]; dfsGraph(int num) { this.num = num; this.graph = new int[num+1][num+1]; this.visited = new boolean[num+1]; } //연결 정점 void putLine(int a, in..