공부하는 블로그

1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net DFS와 BFS를 이용하여 그래프를 탐색하는 과정을 출력하는 문제이다. import java.util.ArrayDeque; import java.util.Queue; import java.util.Scanner; class Main { static int n, m, v; static boolean[][] linked; static boolean[] visit; static StringBuilder sb = new String..

DFS와 BFS는 그래프를 탐색하는 방법이다. 둘의 차이를 간단히 말하자면 깊이(자식)를 우선으로 탐색하냐, 너비(형제)를 우선으로 탐색하냐 이다. DFS (Depth First Search) 깊이 우선 탐색(DFS)은 루트(root) 노드 또는 임의의 노드를 기준으로 시작하여 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 즉, 한 곳을 선택하여 우선적으로 끝까지 탐색한 후에야 다른 인접한 노드를 방문할 수 있다. 이 방법은 그래프의 모든 노드를 방문하고자 할 경우 유용하다. 코드로 구현할 때에는 스택(stack)과 재귀함수를 사용한다. 재귀함수를 이용하여 DFS를 구현하는 과정은 다음과 같다. * 재귀함수 : 자기 자신을 호출하는 함수 0. 시작 노드가 없을 경우에는..

5052번: 전화번호 목록 문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없� www.acmicpc.net 전화번호 목록 중 한 번호가 다른 번호의 접두어가 되는지 판단하는 문제이다. import java.util.Arrays; import java.util.Scanner; class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int tc = sc.nextInt(); for (int i = 0; i < tc; i++) { int n = sc.nextInt(); S..

Queue? 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 형식을 말한다. 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다. Queue Method · add() : 리스트의 끝 부분에 새로운 요소를 추가한다. · remove() : 리스트의 첫 번째 항목을 제거한다. · peek() : 큐에서 가장 위에 있는 항목을 반환한다. · isEmpty() : 큐가 비어 있을 때에 true를 반환한다. Queue Code(JAVA) import java.util.ArrayList; import java.util.List; class MyQueue { private List que = new ArrayL..

Stack? 스택(Stack)은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형구조(LIFO - Last In First Out)로 되어있다. 자료를 넣는 행위를 푸시(Push), 넣어둔 자료를 꺼내는 행위를 팝(Pop)이라고 한다. *LIFO : 나중에 넣은 값이 가장 먼저 나오는 것을 LIFO 구조라 한다. 스택은 프로그래밍 언어마다 라이브러리로 구현되어 있지만 직접 사용자가 연결 리스트를 이용하여 구현해낼 수도 있다. Stack Method · pop() : 스택에서 가장 위에 있는 데이터를 제거한다. · push() : 스택의 가장 위에 데이터를 추가한다. · peek() : 스택의 가장 위에 있는 항목을 반환한다. · isEmpty() : 스택이 비어있을 때에 true를 반환한다. Stack C..