곧죽어도 콛잉

https://www.acmicpc.net/problem/1325 B)은 성립되지 안되는 걸 꼭 짚고 가야한다. 나는 그걸 착각해서 고생을 좀 많이했다 ㅠㅠ 문제를 꼭 제대로 읽자. (나만 바보였을지도...^) bfs로 트리를 순회하는데, 여기서 주목해야할 점이 바로 void가 아니라 int형을 반환한다. 이것도 이전 트리문제와 비슷한데, 재귀를 돌수록 합이 증가해 결국 최종 리턴값은 자식 노드들의 개수 + 1(자기자신)가 된다! 이렇게 최종적으로 나온 리턴값의 최대값을 구하면 된다! 같을 경우에는, 별도의 배열에 넣어주자. #include using namespace std; int N, M, A, B; vector arr[10001]; int vis[10001], res[10001]; int dfs(..

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 1) 인접 리스트를 통해 트리를 완성한다. 이때, root를 따로 지정해준다. 2) 리프노드를 찾는 int dfs(n) 함수를 만들어준다. 이때, dfs(n)는 return 될때 n인 노드가 리프노드라면 1을, 아니면 ret를 출력한다. 2-1) 단, n이 delete_num일 경우, 더이상 함수 진행을 하지 않는다. 2-2) 반복문을 돌때마다 ret값을 갱신해준다. 3) ret를 출력해준다..

https://www.acmicpc.net/problem/2910 2910번: 빈도 정렬 첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다. www.acmicpc.net 1) 빈도수를 저장해야하므로 맵 자료구조를 사용한다. 이때, 맵 자료구조를 하나 더 사용하여 나온 순서도 저장한다. 2) 저장된 맵 자료구조를 정렬해야하므로 vector에 저장해준다. 3) 빈도수 정렬의 규칙에 따라 cmp 함수를 설정하고 sort를 진행한다. 4) vector를 출력한다. 우선 해당 수 : 빈도 수 가 필요하다는 것은 바로 알아차렸을 것이다. 그렇다면 바로 써줘야하는 자료구조는 바로 map이다!!! map을 이용하면 매우..

https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 1) 재귀함수 q(x, y, n)를 설정한다. - 종료조건 : n==1 이 되면 x,y에 해당하는 숫자를 push_back 해준다. - 반복 : x, y부터 x+n,y+n까지 탐색을 시작한다. 만약 x,y에 해당하는 숫자와 다른 숫자가 나온다면, q를 호출하여 4번을 재귀적으로 돌린다. 추가로, 여는 괄호 '(' 를 push_back 해준다. 4번의 재귀가 끝난다면, 닫는 괄호 ')'..

https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 1. 주어진 좌표를 이용해 먼저 MxN 크기의 배열에서 사각형을 색칠한다. (방문표시) 2. 사각형을 색칠하고 나면 MxN 크기의 배열을 순회하며 bfs나 dfs를 해준다. (이때, 영역의 개수를 구한다) 3. bfs나 dfs를 하면서 해당 영역의 넓이를 구해 배열에 추가해준다. 4. 영역의 개수와 sort된 배열을 출력해준다. 이 문제를 풀 때 (N, M)을 보고 가로 길이는..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 1) 배열 전체를 탐색한다. 만약 방문표시(1)가 있거나 양배추가 안심어져있으면(0) 지나간다. 2) 만약 방문을 안했고, 양배추가 심어져있다면, count를 하고, dfs나 bfs를 시행하며 방문표시를 한다. 3) count를 출력한다. 전형적인 연결된 컴포넌트 문제이다. 배열 전체를 순회하며 dfs나 bfs를 시행하며 cnt를 해주면 된다. 이런 최단거리를 구하는 문제가 아니라면 코드가 더 짧은 dfs를 ..