연결요소의 개수 촌수계산 나이트의 이동 유기농배추 토마토 상범빌딩 적록색약 안전영역 스타트링크 숨바꼭질 1. 연결요소의 개수 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 import java.util.ArrayList; import java.util.Scanner; public class Main { private static ArrayList[] edge; private static boolean[] visited; static void dfs(int x){ visited[x] = true; for(int i..
1. 촌수계산 문제 분석(boj.kr/2644)이 문제도 사실 미로찾기 문제와 다를게 없다. 방문체크를 노드기준으로 한다는 것과 다르게. 입력된 상태를 노드로 표현하면 다음과 같다. 이제 BFS를 해야한다. 시작하는 위치는 두 사람의 어느곳이든 상관없다. 나는 7에서 시작한다고 가정하겠다.그렇다면, BFS(7)로 탐색이 시작된다.미로탐색에서 쓰였던 방법처럼, 현재 노드까지의 최단경로에서 +1을 다음노드에 해준다. 7과 연결된 노드는 2와 8이다. 결과적으로 1+1이 된다. 7과 연결된 노드가 모두 방문되면, 다음 노드(q.front())를 꺼내서 연결된 노드를 방문한다. 2와 연결된 노드는 1, 7, 8, 9이다. 하지만 7은 방문되었으므로, 생각치 않는다. 1, 8 ,9의 방문체크를 2+1로 해준다. ..
1. 미로탐색 문제 분석(boj.kr/2178) 이번 문제는 사실 크게 어렵지 않다. 간단한 방법으로 풀 수 있다. 우선, edge는 미로에서 이동할 수 있는 루트를 2차원 배열로 만들어야 한다. visited를 2차원 배열로 만들어야 한다. 우리가 DFS에서 했던 어떤 문제는 1차원 배열의 형태로 만들었다. 그 이유는, 각 노드에 대한 방문이다. 하지만 여기서는, 각 노드에 대해서 방문하는게 아니라, 배열의 위치를 방문하는 것이다.우리는 (1,1)에서 최종 목표로 갈 수 있는 최소 칸수를 구해야 한다. 그래서 탐색을 (1.1)에서 시작한다.화살표의 의미는, 이 바로 다음에 설명하도록 하겠다.아, 너무 당연하지만 0이면 방문하지않음, 0이 아니면 방문했음을 표현했다.현재 상태는, (1,1)에서 방문을 시..
자, 이제 빨리 DFS의 반대 개념인 BFS에 대해 배워보죠.BFS는 너비 우선 탐색(breadth-first search)의 약자고, 역시 컴포넌트의 모든 정점을 한 번씩 순회하는 용도입니다.DFS와 대립되는 성질을 갖고 있으며, 사용되는 곳도 매우 다릅니다.그러나 DFS와 겹치는 용도가 있는데, BFS 역시 컴포넌트의 개수를 세거나 각 컴포넌트의 크기를 구하는 데는 사용 가능합니다. DFS가 깊이를 중시했던 것에 반해 BFS는 넓이를 중시한다는데요.DFS는 한 우물만 계속 파다가 끝을 보고 나서야 다른 곳으로 옮기는 데 반해, BFS는 모든 곳을 똑같이 조금씩 조금씩 팝니다. 저번과 동일한 그래프를 예로 들어봅시다.맨 처음에 0번 정점부터 방문을 시작했을 때, 그 다음 단계에는 DFS에서와는 다르게,..
1. 텀 프로젝트 문제 분석(boj.kr/9466)1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include #include using namespace std; #define MAX_SIZE 100001 int N, edge[MAX_SIZE], cnt;bool visited[MAX_SIZE], finished[MAX_SIZE]; /*다음에 방문할 정점을 방문한 적 있는데, DFS가 끝나지 않는다면(사이클), 다음에 방문 할 정점부터, 나한테 돌아올때까지 더한다.그리고 마지막에 나를 포함하기 위해서 cnt++을 해준다.*/ void dfs(int cur) { visited[c..
1. 안전영역 문제 분석(boj.kr/2468)이 문제는 처음에 낚였다. 왜 height=0, height=maxH일때를 왜 생각하는 건가?솔직히 아직도 잘 모르겠다. 높이가 최대이면, 다 잠겨버리는거 아닌가? 그래서 고려할 가치가 없다고 생각했다.하지만, 높이가 0일때는 구분해야한다. 왜냐면, 전부 높이가 1인 경우가 있기 때문이다.약간 문제의 낚시라고 해야하나 문제 자체는 쉬웠는데, 저 부분에서 좀 애먹었다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include #include #define MAX_SIZE 101 int row[4..
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,..
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. 두더지 문제 분석 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990#include int matrix[101][101];//matrix 초기 사이즈를 크게크게 잡자 1~5정도 더 크게.int homeSize[101];int homeCnt;int matrix_size; /*rangeOverCheck깊이우선탐색을 하면서, 노드(배열의 각각 요소)의 범위를 넘지 않도록 check한다.i와 j는 행과 열..
DFS (Depth-First Search, 깊이 우선 탐색)깊이 우선 탐색은 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 중 하나입니다. 현재 정점과 인접한 간선들을 검사하다가 방문하지 않은 정점을 발견하면 그 간선을 통해 방문하지 은 정점으로 이동하는 것입니다. 이 과정을 반복하다가 더 이상 방문할 수 있는 정점이 없으면 마지막으로 통과한 간선을 통해 뒤로 돌아가서 해당 정점에서 방문할 수 있는 정점을 탐색합니다. 이러한 과정을 반복하여 그래프의 모든 정점을 방문하는 알고리즘이 DFS 알고리즘입니다. 여러분의 이해를 돕기 위해 움직이는 그림으로 그래프를 설명하도록 하겠습니다.위의 그림과 같은 유향 그래프가 존재하고 한 정점에서 여러 개의 정점으로 이동이 가능할 때 정점의 번호가 더 작..