coding tasty house

양 문제설명 행과 열을 입력 받은 다음, #은 울타리 .은 아무것도 없음, o는 양 그리고 v는 늑대를 의미한다. 이때 울타리 공간 안에 양의 수가 늑대의 수보다 많으면 양은 늑대를 밀어 낼 수 있다. 다른 말로는 늑대가 양의 수보다 많거나 같으면 늑대가 양을 처리한다. 따라서 다음 날의 존재하는 늑대와 양의 수를 출력시킨다. 알고리즘 문자열과 행과 열의 값을 입력 받는다. 각 값을 조회하는데, 그 칸을 방문 하지않았고, 울타리가 아닌 경우 DFS 함수로 조회한다. DFS 함수에서는 방문 표시를 하고 늑대, 양의 수를 세며, 울타리는 종료시킨다. 늑대나 양을 센 경우에는 그 구역 내의 다른 칸도 확인하기 위해서 상하좌우로 이동하며 다른 양이나 늑대의 수를 센다. DFS 함수에서 빠져나와서 해당 구역에 늑..

바이러스 문제설명 첫 줄(node)에 컴퓨터의 수, 두 번째 줄(num)에 간선의 수가 주어진다. 그리고 연결관계를 입력 받은 뒤, 1번 컴퓨터부터 시작해서 바이러스에 감염된 컴퓨터의 수를 출력시키는 문제이다. 알고리즘 설명 input을 입력받는다. 연결관계를 2차원 배열에 graph[x][y]=1, graph[y][x]=1에 각각 넣어준다. dfs 함수에서 현재 방문 노드를 매개변수로 받고 반복문을 1부터 노드의 수까지 반복하여 연결된 노드를 찾아 재귀적으로 방문한다. 방문할 때 바이러스에 감염된 컴퓨터의 수도 같이 세어준다. #include #include #include #include using namespace std; #define MAX 101 int graph[MAX][MAX]; bool ..

단지번호 붙이기 문제설명 첫 줄에 주어지는 입력은 지도의 크기(5 node; vector v; for (int i = 0; i > x; for (int j = 0; j < node; j++) graph[i][j] = x[j]-'0'; } for (int i = 0; i < node; i++) { for (int j = 0; j < node; j++) { if (graph[i][j] == 1 && visited[i][j] == 0)//방문 가능한 노드로 재귀 { DFS(i, j); all++;//전체 단지수 측정 v.push_back(cal); } cal = 0;//단지당 집 수 초기화 } } cout

유기농 배추 (DFS) 문제설명 dfs알고리즘을 사용한 문제로 노드간의 연결된 관계를 파악하여 그 갯수를 세는 문제이다. 알고리즘 순서 테스트케이스(T)와 밭의 가로세로 크기(M,N), 간선의 갯수(K)를 입력 받는다. 연결관계를 2차원 graph에 1로 표현한다. 예) 2,3 -> graph[2][3]=1 graph를 반복해서 연결관계가 1이고 현재 방문하지 않은 노드를 방문한다. dfs함수에서 방문했다는 visited[x][y]=1 표현으로 방문 여부를 체크하고 현재 노드에서 상,하,좌,우 연결관계를 재귀적으로 확인한다. 재귀적인 확인을 마친뒤 다시 main 함수로 돌아오면 answer값을 증가시킨다. 여러번 테스트를 위해서 vector에 값을 담아 놓았다. #include #include #incl..

DFS와 BFS문제설명기본적인 DFS&BFS를 구현한다.이때, 정점의 갯수(N) 간선의 갯수(M), 그리고 시작노드(V)를 입력 받는다.dfs와 bfs를 수행하고 난 노드 방문 순서를 출력시킨다.알고리즘 순서DFS의 경우 현재 방문한 노드의 인덱스를 매개변수로 전달반복문을 통해서 방문하지 않았고 연결되어 있는 노드를 재귀적으로 방문한다.BFS의 경우도 동일하고 queue에 현재 방문한 노드를 넣는다.반복문을 통해서 queue가 비어있을 때 까지 맨 앞의 노드를 끄내고, 그 노드와 인접했지만 방문하지 않은 노드를 방문한다.#include #include #include #include #include using namespace std;#define MAX 1001int graph[MAX][MAX];int..