본문 바로가기

Algorithm

 (12)
DFS 문제 분석-3(영역구하기, 음식물 피하기) 1. 영역구하기 문제 분석(boj.kr/2583) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394#include #define MAX_SIZE 101 int paper[MAX_SIZE][MAX_SIZE];int M, N, K;int row[4] = { -1,0,1,0 };int col[4] = { 0,-1,0,1 };int area[MAX_SIZE];int Area_cnt, djtArea; int checkRangeOver(int i,..
DFS 문제 분석-2(적록색약, 연결 요소) Bool을 이용해서 방문체크 하기 1. 적록색약 문제 분석(boj.kr/10026) 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899#include //#include memset을 이용할 수 있다.#define MAX_SIZE 101#define TRUE 1#define FALSE 0 char painting[MAX_SIZE][MAX_SIZE];int bool_visit[MAX_SIZE][MAX_SIZE];int N;..
DFS 문제 분석-1(두더지, 섬, 배추...) DFS의 비슷한 문제 유형을 풀어보고 분석해보자. 1. 두더지 문제 분석 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990#include int matrix[101][101];//matrix 초기 사이즈를 크게크게 잡자 1~5정도 더 크게.int homeSize[101];int homeCnt;int matrix_size; /*rangeOverCheck깊이우선탐색을 하면서, 노드(배열의 각각 요소)의 범위를 넘지 않도록 check한다.i와 j는 행과 열..
깊이 우선 탐색(depth-first search: DFS) DFS (Depth-First Search, 깊이 우선 탐색)깊이 우선 탐색은 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 중 하나입니다. 현재 정점과 인접한 간선들을 검사하다가 방문하지 않은 정점을 발견하면 그 간선을 통해 방문하지 은 정점으로 이동하는 것입니다. 이 과정을 반복하다가 더 이상 방문할 수 있는 정점이 없으면 마지막으로 통과한 간선을 통해 뒤로 돌아가서 해당 정점에서 방문할 수 있는 정점을 탐색합니다. 이러한 과정을 반복하여 그래프의 모든 정점을 방문하는 알고리즘이 DFS 알고리즘입니다. 여러분의 이해를 돕기 위해 움직이는 그림으로 그래프를 설명하도록 하겠습니다.위의 그림과 같은 유향 그래프가 존재하고 한 정점에서 여러 개의 정점으로 이동이 가능할 때 정점의 번호가 더 작..

티스토리툴바