DFS

DFS / BFS DFS와 BFS를 알기 위한 그래프 개념 그래프란? 노드(Node)와 간선(Edge)으로 표현되며 이때 노드를 정점이라고 한다. 그래프 탐색이란? 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 먼저 그래프에 대해 알아보자. 두 노드가 엣지로 연결되어 있을 때 ex) 위 그림에서 A-B 가 연결되어있는데, 이때, '두 노드가 인접한다(Adjacent)' 라고 표현한다. 프로그래밍에서는 그래프를 표현하는 2가지 방식이 있다. 1. 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현 2. 인접 리스트(Adjaceny List) : 리스트로 그래프의 연결 관계를 표현 인접 행렬로 표현한 그래프 0 1 2 0 0 5 7 1 5 0 무한 2 7 무..

N * M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 다음의 4 * 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다. [입력 조건] 첫 번쨰 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1

스택과 큐, 재귀 함수는 DFS와 BFS에서 가장 중요한 개념이라 DFS/BFS를 배우기에 앞서 간단하게 설명했다. 이제부터 DFS/BFS 알고리즘을 살펴보겠다. DFS DFS는 Depth-First Search, 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS를 설명하기 전에 먼저 그래프(Graph)의 기본 구조를 알아야 한다. 그래프는 노드(Node)랑 간선(Edge)으로 표현되며 이때 노드를 정점(Vertex)이라고도 말한다. 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 또한 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다(Adjacent)'라고 표현한다. 여기에서 갑자기 노드와 간선이라는 생소한 단어가 나와서..

탐색(Search)란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로 DFS와 BFS를 꼽을 수 있는데, 이 두 알고리즘의 원리를 제대로 이해해야 코딩 테스트의 탐색 문제 유형을 풀 수 있다. 그런데 DFS와 BFS를 제대로 이해하려면 기본 자료구조인 스택과 큐에 대한 이해가 전제되어야 하므로 사전 학습으로 스택과 큐, 재귀 함수를 간단히 정리하고자 한다. 자료구조(Data Structure)란 '데이터를 표현하고 관리하고 처리하기 위한 구조'를 의미한다. 그중 스택과 큐는 자료구조의 기초 개념으로 다음의 두 핵심적인 함수로 구성된다. 삽입(Push) : 데이터를 삽입한다. 삭..