C++_Algorithm/DFS

문제입출력문제 요약무방향 그래프에서 연결된 요소들의 개수를 찾는 것이다.무방향 그래프에서는 2차원 벡터를 사용해야 한다. 2차원 벡터2차원 벡터라는 것에대해 이해가 잘 안갔는데 자바의 List형태에 배열이랑 구조가 비슷하다.예제 입력 1을 2차원 백터로 표현하자면이런 식으로 표현이 될 것이다.이제 1부터 시작하여 1의 인접 리스트인 2,5를 dfs 진행하면 된다.코드#include #include #include using namespace std;vector V[1000];bool visited[1000];int cnt = 0;int N, M;int a, b;void init() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}void df..

문제입출력문제 요약정점이 5개, 간선이 5개, 1번부터 출발한다.정점과 연결된 관계는 (1,4), (1,2), (2,3), (2,4), (3,4)로 연결되어 있다. 이런 그림으로 양방향 연결되어 있다.방문할 때는 인접 정점을 오름차순으로 정렬 후 방문한다고 했으니 정렬을 하자면이런 식으로 정렬이 되어 있을 것이다. 1번부터 방문을 한다면1번 -> 2번 -> 3번 -> 4번, 5번은  X 순으로 방문하게 될 것이다.코드#include #include #include using namespace std;vector V[100001];int visited[100001];int ans[100001];int depth = 1;void dfs(int x) { visited[x] = 1; ans[x] = depth+..

문제입출력문제 요약적록색약은 빨강(R), 초록(G)를 차이를 구분하지 못한다고 한다. 즉 적록색약이 봤을 때는 R과 G를 동일선상에 놓아야한다.출력 값들을 보면 적록색약이 아닌 사람이 봤을 때의 구역 개수, 적록색약인 사람이 봤을 때 구역의 수를 출력해야한다.코드 구현 순서는 1. 적록색약이 아닌 사람이 봤을 때의 dfs 실행2. 적록색약의 dfs를 하기 전 G -> R 로 바꾸기3. visited 배열 false로 다시 초기화4. 적록색약의 dfs 실행코드#include #include using namespace std;int dx[4] = { -1,0,1,0 };int dy[4] = { 0,1,0,-1 };char map[100][100];bool visited[100][100];int N;int ..

문제입출력문제 요약이 문제는 백준 1012 유기농 배추 문제에서 대각선 방향으로 이동하는 조건만 추가한 문제이다.https://dongyeop00.tistory.com/108 C++ [Algorithm] - 백준 1012 유기농 배추문제 간단하게 설명하자면 상하좌우 네 방향에 다른 배추가 위치한 경우 서로 인접하다. 즉 1덩어리로 본다.위 그림을 보면 총 5덩어리다. 코드#include #include using namespace std;int testCase, M, N, K;int xdongyeop00.tistory.com코드는 위 문제와 동일하나 dx, dy 배열에서 대각선으로 이동하는 값만 추가되었다.코드#include #include using namespace std;int dx[8] = { -..

문제입출력문제 요약이 문제는 dfs가 몇번 돌아가는지, dfs 1번 돌아갈 때 몇번 탐색하는지를 구현하는 문제이다.dfs 개념과 dfs의 재귀함수 과정을 안다면 쉽게 풀 수 있다. 코드#include #include #include #include using namespace std;int map[25][25];bool visited[25][25];int dx[4] = { -1,0,1,0 };int dy[4] = { 0,1,0,-1 };int N, house = 1;vector seq;void dfs(int x, int y) { visited[x][y] = true; for (int i = 0; i = 0 && ny >= 0) { if (map[nx][ny] == 1 && !visited[nx][ny..

문제입출력문제 요약(0,0)으로 시작해서 (m,n)까지 갈 수 있는 경로를 구하는 문제이다.단 이동할 수 있는 조건은 다음 좌표의 위치값이 현재 좌표의 위치값보다 작아야한다.이 조건은 dfs 함수에서 (map[x][y] > map[nx][ny])로 구현하면 될 것 같다. 모든 경로의 수를 구해야 하니 살짝 dp 메모제이션 기법을 사용하면 좋을 것 같다. [dp 배열]322211  111  1 1111목적지 문제에서 주어진 모든 경로들이 지나가는 곳에 1씩 더하면서 dfs를 시작하면최종적으로 이런 dp 배열 형태가 만들어질 것이다.코드#include #include using namespace std;int map[501][501];int visited[501][501];int dx[4] = { -1, 0..