문제https://www.acmicpc.net/problem/11725풀이과정각 노드의 연결 상태를 입력으로 받고 각 노드의 부모노드 번호를 출력하는 문제이다. 트리의 입력을 그래프처럼 인접리스트로 받은 후에 BFS로 탐색하며 parent 배열에 부모노드 번호를 저장하면 된다.처음 예제입력을 BFS로 탐색해보면 처음 1 다음에는 큐에 4와 6이 들어가며 parent[4]와 parent[6]의 값은 부모노드 번호인 1이 들어가게 된다. 다음 과정을 살펴보면 큐의 front값이 4이므로 parent[2]와 parent[7]의 값은 부모노드 번호인 4로 된다. 이렇게 BFS를 통하여 부모노드를 저장하는 방법으로 해결할 수 있는 문제였다.소스코드#include #include #include using name..
문제https://www.acmicpc.net/problem/1991풀이과정기본적인 트리의 순회과정 구현을 묻는 문제다. 전위 순회(preorder)는 root->left->right 중위 순회(inorder)는 left->root->right 후위 순회(postorder)는 left->right->root어떻게 구현을 해야할지 조금만 생각해보면 쉽게 풀 수 있는 문제다. 문제에서 입력되는 트리는 자식을 최대 2개로 가지는 이진 트리이므로 배열로 트리를 표현할 수 있다. a[26][2] 라는 배열을 선언하여 각 알파벳을 부모노드로 가지는 자식을 저장하면 된다. 각 순회의 구현은 재귀호출을 통해 구현하였다.소스코드#include using namespace std; int a[26][2]; int N; v..
문제https://www.acmicpc.net/problem/2146풀이과정단지번호붙이기와 토마토 문제를 합친 개념으로 보면 된다. 제한시간을 한시간으로 두고 풀어보려고 했지만 섬이 있는 곳들을 그룹으로 만드는거 이후 거리를 계산하는 방법이 떠오르지 않아서 검색을 통해 해결했다. 섬들을 그룹으로 묶어서 g 배열에 저장한다.각 그룹마다 BFS를 통해 거리를 계산해 grup_dis 배열에 저장한다.원래 입력값으로 저장되어있는 a 배열과 그룹으로 나누어 저장한 g 배열을 이용하여 현재 그룹의 아닌 다른 섬까지의 거리를 계산한다.최소값을 출력한다. 3번 과정을 구현하는 소스코드를 보고도 이해하기 힘들었다. DFS, BFS 활용 문제는 정말 필수로 나오는 문제이니 관련 문제를 찾아서 더 많이 풀어봐야겠다.소스코드..
문제https://www.acmicpc.net/problem/7576풀이과정BFS로 해결할 수 있는 문제. 익은 토마토부터 BFS를 시작하여 거리를 재는 식으로 풀이하면 된다. 문제에서 토마토가 모두 익지 못할 경우 -1을 출력하라고 했는데 이 예외를 까먹고 하지 않아서 몇 번 틀렸다.소스코드#include #include using namespace std; #define MAX 1000 int N, M; int map[MAX][MAX]; int tomato[MAX][MAX]; int dx[4] = { 0,0,-1,1 }; int dy[4] = { -1,1,0,0 }; int main() { ios::sync_with_stdio(false); cin >> M >> N; queue q; for (int ..
문제https://www.acmicpc.net/problem/2178풀이과정시작점부터 이동할 수 있는 칸을 이용해서 (N,M)까지 가야한다. 주어진 칸을 최소한으로 이용하며 도착할 수 있을 때 최소 칸 수를 출력 해야한다.기본적인 BFS 문제라고 한다. DFS로는 풀 수 없는 문제다. 문제를 풀다가 DFS와 BFS를 어떨 때 써야 좋을까 라는 생각이 들어서 검색해봤다.DFS는 사이클 탐지, 위상정렬 BFS는 최소신장트리, 최단경로소스코드#include #include #pragma warning(disable:4996) #define MAX 100 using namespace std; int map[MAX][MAX]; int ans[MAX][MAX]; bool chk[MAX][MAX]; int N, M;..
문제https://www.acmicpc.net/problem/4963풀이과정2차원 배열에서 섬을 1이라고 했을 때 상하좌우와 대각선 4가지 경우를 다 검사하는 dfs를 구현해서 풀이했다. 앞에서 풀어본 단지번호붙이기를 풀어서 그런지 응용해서 풀 수 있었다.소스코드#include using namespace std; int map[51][51]; int visited[51][51]; int dx[8] = { 0,0,1,-1,-1,-1,1,1 }; int dy[8] = { 1,-1,0,0,-1,1,-1,1 }; int w, h; void dfs(int x,int y) { visited[y][x] = 1; for (int k = 0; k < 8; k++) { int nx = x + dx[k]; int ny =..
문제https://www.acmicpc.net/problem/1003풀이과정오늘 문제 푸는 날인지 모르고 있다가 급하게 푸느라 조금 쉬운 문제를 풀었다. 피보나치 함수를 fibonacci(N) 이라고 두고 재귀로 구하는 함수가 주어지는데 이 때 fibonacci(0)과 fibonacci(1)이 몇 번 호출되는지 구하면 되는 문제이다. 그냥 호출될 때마다 배열에 숫자를 올려서 나중에 출력했다.소스코드#include using namespace std; int cnt[2]; int fibonacci(int n) { if (n == 0) { cnt[0]++; } else if (n == 1) { cnt[1]++; } else { return fibonacci(n - 1) + fibonacci(n - 2); }..
문제https://www.acmicpc.net/problem/1463풀이과정기본적인 DP 문제 중 하나이다. D[i] = i를 1로 만드는 데 필요한 최소 연산 횟수라고 놓고 경우의 수를 생각해보니 아래와 같았다. i가 3으로 나누어 떨어질 경우 D[i/3] + 1 i가 2로 나누어 떨어질 경우 D[i/2] + 1 i에서 1을 빼는 경우 D[i-1] + 1 이렇게 총 세 가지이며 세 가지의 경우 중 최소값을 찾으면 된다.소스코드#include using namespace std; #define MAX 1000001 int D[MAX]; int solution(int N) { if (N==1) return 0; if (D[N] > 0) return D[N]; D[N] = solution(N - 1) + 1..
문제https://www.acmicpc.net/problem/2667풀이과정DFS로 이차원 배열을 모두 탐색하며 끊기는 부분마다 단지번호를 주면 된다. 앞에서 풀었던 DFS를 이용해 이분 그래프의 개수를 출력하는 문제와 비슷하게 풀면 될 것 같아서 그렇게 풀어봤다. 이런 문제는 DFS,BFS 구현에 대해 아무런 지식이 없을 때 절대 못 풀었었는데 이제는 조금 감이 오는 것 같아서 좋다.소스코드#include #include #include #include using namespace std; vector a[26]; int visited[26][26]; int dx[4] = { 0,0,1,-1 }; int dy[4] = { 1,-1,0,0 }; int n; int ans[25 * 25]; // n 최대값..