새발블로그

1. 트리(Tree)란?트리는 노드(Node)가 계층적으로 연결된 비선형 자료구조입니다. 최상위에는 루트(Root)가 있고, 각 노드는 0개 이상의 자식 노드를 가진다. 비선형 자료구조란?데이터가 단순히 일렬로 연결되는 것이 아니라 계층적 또는 네트워크 형태로 연결된 구조이다.2. 트리 관련 기본 용어노드(Node): 트리를 구성하는 기본 단위루트 노드(Root Node): 트리의 시작점, 부모가 없는 노드부모 노드(Parent Node): 다른 노드를 자식으로 가지는 노드자식 노드(Child Node): 특정 부모 노드에 연결된 하위 노드형제 노드(Sibling Node): 같은 부모를 가진 노드들리프 노드(Leaf Node): 자식이 없는 노드(끝점)서브트리(Subtree): 특정 노드를 루트로 하는..

1. 거리 측정의 핵심 원리다음 노드의 거리 = 현재 노드의 거리 + 1, 즉 거리 값을 퍼뜨리는 bfs가 유리2. BFS로 거리 측정하기BFS의 특징너비 우선 탐색: 가까운 곳부터 먼저 방문한 번 방문한 노드에는 항상 최단거리로 도달방법 1. distance 배열만 사용int[][] distance = new int[rowLen][colLen];for (int[] row : distance) Arrays.fill(row, -1); // -1: 미방문Queue q = new LinkedList();q.add(new int[]{startR, startC});distance[startR][startC] = 0;while (!q.isEmpty()) { int[] curr = q.poll(); for..

암시적 그래프에서 도착점 찾기 (BFS & DFS 활용)1. BFS를 활용한 도착점 탐색BFS는 가까운 위치부터 차례대로 탐색따라서 큐에서 꺼낸 현재 위치가 도착점인지 확인하고, 맞다면 즉시 탐색을 종료할 수 있다.현재 위치: (r, c)목표 위치: (endR, endC)구현 흐름현재 위치가 도착점인지 확인if (r == endR && c == endC) { return true; }모든 위치를 탐색했는데도 도달하지 못하면 실패 처리return false;예제 코드import java.util.*;public class BFSSearch { public static void main(String[] args) { int[][] grid = { {1, 1, 0, 1, ..

DFS와 BFS를 활용한 네트워크(연결된 그룹) 개수 구하기1. 연결된 그룹을 세는 기본 개념암시적으로 표현된 그래프에서도 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)를 이용해 연결된 덩어리(그룹, 네트워크)의 개수를 셀 수 있다.DFS나 BFS를 한 번 실행하면 하나의 네트워크 전체를 방문하게 된다.아직 방문하지 않은 노드를 찾았다면, 새로운 네트워크의 시작점이다.즉, 네트워크 수를 구한다는 건 그래프를 순회하며 새로운 연결 그룹이 등장할 때마다 count를 하나씩 증가시키는 것과 같다.2. 네트워크 개수 세는 절차그래프의 모든 좌표를 순회특정 조건을 만족하는 노드를 찾음 (예: 값이 1)해당 노드를 아직 방문하지 않았다면 DFS/BFS 실행탐색이 끝나면 네트워크 개수 +1모든 노드를 확인할 때..

int[][] grid = { {1, 1, 1, 1}, {0, 1, 0, 1}, {0, 1, 0, 1}, {1, 0, 1, 1}};public class ImplicitGraphDFS { static boolean[][] visited; static int[][] grid; static int[] dr = {1, -1, 0, 0}; static int[] dc = {0, 0, 1, -1}; static int rowLength; static int colLength; public static boolean isValid(int r, int c) { return 0

int[][] grid = { {1, 1, 1, 1}, {0, 1, 0, 1}, {0, 1, 0, 1}, {1, 0, 1, 1}};import java.util.*; public class ImplicitGraphBFS { static boolean[][] visited; static int[][] grid; static int[] dr = {0, 1, 1, 1, 0, -1, -1, -1}; static int[] dc = {1, 1, 0, -1, -1, -1, 0, 1}; static int rowLength; static int colLength; public static boolean isValid(int r, int c) { ..

1. 암시적 그래프 vs 인접 리스트 그래프명시적 그래프: 인접 리스트 방식명시적 그래프에서는 노드 간의 연결 정보를 미리 저장해두고 탐색에 활용대표적인 방식이 인접 리스트for (int nextVertex : graph.get(curVertex)) { // 현재 노드(curVertex)에서 연결된 노드(nextVertex)로 이동}위 코드처럼 graph.get(curVertex)를 순회하면, 연결된 노드들을 바로 얻을 수 있어 간단하게 탐색이 가능,즉, 미리 구성된 연결 관계에 따라 nextVertex를 직접 조회하는 방식암시적 그래프: 동적으로 연결 관계 판단암시적 그래프에서는 연결 정보를 저장하지 않고, 탐색 중에 직접 판단하여 연결 여부를 결정for (int i = 0; i 방향 벡터▸ 상..

암시적 그래프란?그래프는 보통 인접 행렬이나 인접 리스트와 같은 자료구조로 표현함암시적 그래프는 이러한 방식 없이, 문제의 조건을 바탕으로 노드와 간선을 유추하며 탐색하는 방식미로 탐색, 퍼즐, 최단 거리 문제 등에서 자주 등장..1. 암시적 그래프의 개념암시적 그래프는 노드와 간선을 명시적으로 저장하지 않고, 탐색 과정에서 동적으로 판단값이 0이면 이동 가능 (길)값이 1이면 이동 불가 (벽)상, 하, 좌, 우로만 이동 가능이런 미로는 처음에는 단순한 2차원 배열처럼 보이지만, 값이 0인 좌표를 노드, 상하좌우 이동 가능 조건을 간선으로 간주하면 그래프 구조로 해석할 수 있다.2. 암시적 그래프에서의 노드와 간선암시적 그래프에서는 별도의 노드 번호가 없습니다. 좌표 자체가 노드의 역할을 한다.예를 들어..