백트래킹 문제입니다. DFS를 통해서 수를 하나씩 입력해 나가면서 길이가 m이 되면 출력했습니다. #include #include #include #include #include using namespace std; int n, m; int arr[10]; vector v; void DFS(int x) { v.push_back(x); if (v.size() == m) { for (int i = 0; i < v.size(); ++i) { printf("%d ", v[i]); } printf("\n"); v.pop_back(); return; } for (int i = 1; i
BFS문제입니다. 1,1에서 N,M까지 가는데 최단 경로를 구하는 문제입니다. 0은 이동할 수 있는 곳이고, 1은 얼음으로 이동할 수 없습니다. 가는 도중에 얼음을 최대 한개까지 깨고 이동할 수 있습니다. 큐에 현재 위치와 경로 거리, 얼음을 깼는지의 여부를 저장해두었습니다. 얼음을 깼는지 여부에 따라서 BFS를 돌면서 얼음을 만났을 때 얼음을 부수고 가는 경우에 대해서도 체크할 수 있었습니다. #include #include #include #include #include #define MAX 987654321 using namespace std; int n, m; int countNum = MAX; int map[1010][1010]; int visit[1010][1010][2]; int moveX[..
BFS문제입니다. 익은 토마토는 다음날 상, 하, 좌, 우, 위층, 아래층의 토마토를 익게합니다. (익지 않은 토마토 제외) 이 때 토마토가 전부 익는데 걸리는 최소날짜를 구해야합니다. 숫자가 1인 부분을 큐에 넣어놓고 빼면서 주변이 0인곳을 탐색하는 방식으로 BFS를 사용하여서 문제를 풀었습니다. 0인곳을 탐색하면 그 위치를 큐에 넣고 방문을 했다고 처리해줍니다. 큐가 비어있게 되면은 배열에 0이 있는지 확인하고 없으면 카운트한 횟수를 출력하고, 있으면 -1을 출력합니다. #include #include #include using namespace std; int map[110][110][110]; int moveX[4] = { 0, 1, 0, -1 }; int moveY[4] = { 1, 0, -1,..
DFS, BFS문제입니다. 익은 토마토는 다음날 상, 하, 좌, 우의 토마토를 익게합니다. (익지 않은 토마토 제외) 이 때 토마토가 전부 익는데 걸리는 최소날짜를 구해야합니다. 숫자가 1인 부분을 큐에 넣어놓고 빼면서 주변이 0인곳을 탐색하는 방식으로 BFS를 사용하여서 문제를 풀었습니다. 0인곳을 탐색하면 그 위치를 큐에 넣고 방문을 했다고 처리해줍니다. 큐가 비어있게 되면은 배열에 0이 있는지 확인하고 없으면 카운트한 횟수를 출력하고, 있으면 -1을 출력합니다. #include #include #include using namespace std; int map[1010][1010]; int moveX[4] = { 0, 1, 0, -1 }; int moveY[4] = { 1, 0, -1, 0 }; q..
BFS로 문제를 풀었습니다. 1,1에서부터 N,M까지 BFS를 통해 몇번만에 가는지 확인한 후 출력하였습니다. #include #include #include #include #include using namespace std; int moveX[4] = { 0, 1, 0, -1 }; int moveY[4] = { 1, 0, -1, 0 }; int main(int argc, char *argv[]) { int n, m; int map[110][110]; int visit[110][110]; int a, b; int x, y; int c; string s; queue q; cin >> n >> m; memset(map, 0, sizeof(map)); memset(visit, 0, sizeof(visit))..
1번 컴퓨터와 연결되어 있는 컴퓨터의 개수를 찾는 문제입니다. 1번 컴퓨터에서 DFS를 통해 연결되어 있는 컴퓨터를 탐색했습니다. 같은 컴퓨터를 탐색할 경우를 제외하기 위해 visit 배열에 이미 방문하였으면 체크를 해두었습니다. #include #include #include #include #include using namespace std; vector v[110]; int visit[110]; int c = 0; void DFS(int x) { visit[x] = 1; ++c; for (int i = 0; i < v[x].size(); ++i) { if (!visit[v[x][i]]) { DFS(v[x][i]); } } } int main(int argc, char *argv[]) { int n,..
스택에 여러가지 기능을 더 추가한 문제입니다. 함수를 입력받고 숫자 testcase를 입력받습니다. 그리고 수를 입력 받는데 이 수는 처음 stack에 들어가게 될 수이며 입력 받은 함수들을 순서대로 실행시켜서 나오는 결과를 출력하여야 합니다. testcase만큼 반복하고 다시 함수를 받는 상태로 돌아갑니다. 이는 QUIT를 입력받을 때 까지 계속 반복해서 진행됩니다. 오류가 날 경우 ERROR를 출력해줍니다. (0으로 나누거나, 값을 초과하거나, 결과값이 하나가 아니거나, 비어있는데 호출하는 등) 그 외에는 결과값을 출력합니다. #include #include #include #include #include #include #define MAX 1000000000 using namespace std; ..
우선순위 큐 문제입니다. 가운데 값을 구하기 위해 우선순위 큐를 두개 만들어 주었습니다. pqMin : 작은 값들 저장 (내림차순) pqMax : 큰 값들 저장 (오름차순) 새로운 값이 들어왔을 때 pqMax.top보다 크면 pqMax에 넣어주고 pqMin.top보다 작으면 pqMin에 넣어줍니다. 만약 넣고나서 아래의 조건이 성립하지 않으면 1. pqMax == pqMin + 1 2. pqMax == pqMin 많은 쪽에서 적은쪽으로 top의 위치의 숫자를 옮겨 줍니다. #include #include #include #include #include #include using namespace std; int main(int argc, char *argv[]) { int n; int num; prior..