[TIL][02.20] 그래프, DFS, BFS, 인접행렬, 인접리스트

2025. 2. 21. 08:33· [LG 유플러스] 유레카/Today I Learned
목차
  1. 그래프
  2. DFS
  3. BFS
  4. 인접 행렬 vs 인접 리스트
  5. 도전문제
  6. 개인 과제

그래프

정점 : 그래프 노드 또는 점

간선 : 정점 간의 연결, 부모-자식 개념 없음

가중치 : 간선(엣지)에 할당된 값

차수 : 정점에 연결된 간선의 수

진입 차수 : 방향 그래프에서 특정 정점으로 들어오는 간선의 수

진출 차수 : 방향 그래프에서 특정 정점에서 나가는 간선의 수

경로 :두 정점 간에 존재하는 간선의 연속

사이클 : 시작 정점에서 출발하여 다시 시작 정점으로 돌아오는 경로. 트리와 가장 큰 차이

연결 그래프 : 모든 정점이 서로 연결된 그래프

포화 그래프 : v개의 정점을 가지는 그래프는 최대 V * (V-1) / 2 간선이 가능

부분 그래프 : 원래 그래프의 일부 정점과 간선으로 구성된 그래프

방향 그래프 : 간선에 방향이 있는 그래프

무방향 그래프 : 간선에 방향이 없는 그래프

 

DFS

최대한 깊이 들어간 후, 더 이상 갈 곳이 없으면 되돌아오는 방식

그림 출처 : https://sethuram52001.medium.com/data-structures-and-algorithms-undirected-graph-processing-491d4fdefad0

BFS

현재 노드에서 가까운 노드를 먼저 탐색하고, 점차 멀리 탐색하는 방식

그림 출처 : https://takeuforward.org/graph/breadth-first-search-bfs-level-order-traversal/

인접 행렬 vs 인접 리스트

그래프를 표현하는 방법에는 인접 행렬(Adjacency Matrix) 과 인접 리스트(Adjacency List) 가 있음

인접 행렬 : 2차원 배열을 사용하여 그래프의 연결 정보를 저장, 연결되지 않은 노드 정보도 저장

인접 리스트 : 각 노드마다 연결된 노드 리스트를 저장, 연결된 노드만 저장하므로 메모리 절약 가능

 

도전문제

백준 17478 재귀함수가 뭔가요?

 

[JAVA]SWEA - 1873. 상호의 배틀필드 (D3)

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { static int x, y, H, W; static char[][] map; static char direction; public static void main(String[] args) throws

leeemingyu.tistory.com

SWEA 1954 달팽이 숫자

 

[JAVA]SWEA - 1954. 달팽이 숫자 (D2)

package graph;import java.util.Scanner;public class Main { static int[] dr = { 0, 1, 0, -1 }; static int[] dc = { 1, 0, -1, 0 }; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int t = 1; t = N || r

leeemingyu.tistory.com

SWEA 1873 상호의 배틀필드

 

[JAVA]SWEA - 1873. 상호의 배틀필드 (D3)

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { static int x, y, H, W; static char[][] map; static char direction; public static void main(String[] args) throws

leeemingyu.tistory.com

개인 과제

프로그래머스 최댓값과 최솟값

 

[JS]프로그래머스 - 최댓값과 최솟값 (Lv.2)

나의 풀이function solution(s) { var answer = ''; let arr = s.split(" "); let min = parseInt(arr[0]); let max = parseInt(arr[arr.length-1]); for(i of arr){ if(min > parseInt(i)){ min = parseInt(i); }else if (max 주어진 문자열을 split을 통해

leeemingyu.tistory.com

프로그래머스 - 카펫

 

[JS]프로그래머스 - 카펫 (Lv.2)

나의 풀이function solution(brown, yellow) { var answer = []; for(i = 1; i b-a); return answer;}전체 격자의 개수가 brown + yellow가 맞는지 확인바깥쪽 brown을 제외한 안쪽 부분이 yellow가 맞는지 확인맞는지 확인 후 저

leeemingyu.tistory.com

 

 

 

 

'[LG 유플러스] 유레카 > Today I Learned' 카테고리의 다른 글

[TIL][02.24] MST, Kruskal, Prim, Dijkstra  (0) 2025.02.25
[TIL][02.21] 그래프, 트리, BFS, DFS, 스택, 큐  (0) 2025.02.24
[TIL][02.19] 비선형 자료구조, 트리, 이진트리, 이진검색, 분할정복  (0) 2025.02.20
[TIL][02.14] Stack, Queue, PriorityQueue, Heap, Scanner  (0) 2025.02.16
[TIL][02.13] 재귀, Serialization, 배열, Exception  (0) 2025.02.13
  1. 그래프
  2. DFS
  3. BFS
  4. 인접 행렬 vs 인접 리스트
  5. 도전문제
  6. 개인 과제
'[LG 유플러스] 유레카/Today I Learned' 카테고리의 다른 글
  • [TIL][02.24] MST, Kruskal, Prim, Dijkstra
  • [TIL][02.21] 그래프, 트리, BFS, DFS, 스택, 큐
  • [TIL][02.19] 비선형 자료구조, 트리, 이진트리, 이진검색, 분할정복
  • [TIL][02.14] Stack, Queue, PriorityQueue, Heap, Scanner
leeemingyu
leeemingyu
leeemingyu
ye
leeemingyu

블로그 메뉴

  • GitHub
  • Instagram
    전체
    오늘
    어제
    • 전체보기 (68)
      • GDSC (4)
        • 실시간 채팅 구현 (4)
      • [LG 유플러스] 유레카 (63)
        • Today I Learned (37)
        • 코딩테스트 (22)
        • 프로젝트 (4)

    공지사항

    인기 글

    최근 댓글

    최근 글

    hELLO · Designed By 정상우.v4.2.2
    leeemingyu
    [TIL][02.20] 그래프, DFS, BFS, 인접행렬, 인접리스트
    상단으로

    티스토리툴바

    단축키

    내 블로그

    내 블로그 - 관리자 홈 전환
    Q
    Q
    새 글 쓰기
    W
    W

    블로그 게시글

    글 수정 (권한 있는 경우)
    E
    E
    댓글 영역으로 이동
    C
    C

    모든 영역

    이 페이지의 URL 복사
    S
    S
    맨 위로 이동
    T
    T
    티스토리 홈 이동
    H
    H
    단축키 안내
    Shift + /
    ⇧ + /

    * 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.