1일1알

1. root부터 탐색하면서 삭제할 노드의 부모 노드를 알아낸다. 2. 삭제할 노드를 dfs를 이용하여 제일 밑에있는 자식 노드부터 차례로 삭제한다. 3. 2번이 끝났으면 삭제할 노드의 자식들은 모두 삭제가 된 상태이기 때문에 1번에서 파악한 부모 노드를 이용하여 삭제할 노드를 삭제한다. 4. root부터 탐색하면서 리프 노드의 갯수를 알아낸다. 예외) 삭제할 노드가 root노드라면 부모 노드가 없기때문에 0을 출력하고 프로그램을 종료한다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef lon..

어렵지 않은 bfs 탐색 문제이다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int f, s, g, u, d; vector found(1000001, false); int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> f >> s >> g >> u >> d; queue q; q.push({ s,0 }); found[s] = true; int ans = -1; bool..

bfs로 풀었는데, 위치를 찾았는지를 저장하는 found배열을 찾았는지 여부와, 얼마만에 찾았는지 시간의 정보를 함께 저장해서 찾았다고 무조건 건너뛰는 것이 아니라 얼마만에 찾았는지 비교하여서 만약 지금 큐에 넣으려는 경로가 더 빠르다면 이미 찾은 위치라고 하더라도 큐에 넣어주었다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int n, k; vector found(100001, { false,0 }); int main() { ios_base::sync_with_s..

a에서 b로 변환되는 경우를 bfs를 통해 탐색하였고, 탐색하는 과정에서 parent벡터를 만들어서 어떤 수에서 어떤 레지스터를 사용해서 값이 나왔는지를 저장하였다. 탐색이 끝났을 때 parent벡터를 이용해 역추적해서 사용된 레지스터들을 알아낼 수 있다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int Register(int num, int val) { int ret; int tmp; switch (num) { case 0: ret = (val * 2) % 10..

처음 풀어보는 플래티넘 등급의 문제이다. 푸는 방법을 생각해내는 게 쉽지 않았다. 첫 번째 줄의 전구를 누르거나 누르지 않는 모든 경우 : 2^10 = 1024 이 경우들에서 시작하여 다음 줄에서부터는 자신의 위쪽이 켜져 있으면 끄고, 아니면 넘어간다. = 10) continue; if (nextCol = 10) continue; tmp_board[nextRow][nextCol] = !tmp_board[nextRow][nextCol]; } } void BT(int idx) { if (idx > 9) { bool isAns = true; int cnt = 0; vector tmp_board(10, vector(10)); for (int i = 0; i < 10; i++) { f..

1. 배양액을 뿌릴 수 있는 땅의 그룹을 만든다. (예제 2의 입력을 예로 들면 (0, 0), (2, 0), (2, 2)) 2. 배양액을 뿌릴 수 있는 땅의 그룹 중 r + g 만큼의 땅의 그룹들을 백트래킹을 이용하여 모두 찾는다. (예제 2의 입력을 예로 들면 g는 2, r는 1이어서 r + g는 3 이기 때문에 1번과 같다.) (만약 g = 1, r = 1 이었다면 r + g = 2 이기 때문에 (0, 0), (2, 0) 과 (0, 0), (2, 2) 과 (2, 0), (2, 2) 세 가지 경우가 나옴) 3. 2에서 찾은 그룹을 r 그룹과 g 그룹으로 나눈다. (예제 2의 입력을 예로 들면 g는 2, r는 1이기 때문에 g : (0, 0), (2, 0) , r : (2, 2) g : (0, 0), (..