본문 바로가기

전체 글

 (122)
[백준 1068]트리 문제: https://www.acmicpc.net/problem/1068 1) 문제분류-트리 2)문제 해결- vector에 부모노드에 연결되어있는 자식노드들을 담아 연결을 시킨다.- DFS를 통해서 모든 리프노드를 조사를 하는데, 제거할 노드를 만났을때 return 함으로써 그 부분만 탐색을 안하면 된다.- DFS로 탐색을 할때에는 해당노드의 자식노드들의 개수가 0개라면 Leaf노드이므로 개수를 세어준다. #include #include using namespace std; vector tree[51];int n,root,ans, x;void search(int cur) {if (cur == x) return;int ok = 0;for (int i = 0; i < tree[cur].size();i++){..
[백준 4803] 트리 문제 : https://www.acmicpc.net/problem/4803 1)문제 분류- 트리 2)문제 해결- 처음에는 어떻게 부분트리의 개수를 알수 있을까.. 고민을 했다..고민끝에.. 해답을 봐버렸다! 해답을 본 결과, 이 문제는 트리의 성질을 이용해야하는데, 트리의 성질중에 트리는 정점이 n개, 간선이 n-1개 일때 성립하는게 있다. 그래서, 각 정점마다 정점의 개수를 구하고, 간선의 개수를 구해서 비교하면 트리가 성립되는지 안되는지를 알수있는 문제였다! 정점의 개수와 간선의 개수를 구하는 방법은 dfs로 해결 할 수가 있었는데, 정점의 개수는 연결되어있는 정점을 찾아갈때마다 cnt를 +1하는 방식으로 개수를 구할수 있다 간선의 개수 cnt를 +해당 노드에 연결 되어있는 노드의 개수를 더하면 구할..
[백준 11725]트리의 부모 찾기 문제: https://www.acmicpc.net/problem/11725 1)문제분류- 트리 2)문제 해결-각 정점을 서로 연결 짓는다.- 루트 1에서 시작하여 BFS로 탐색하여 노드들의 부모를 파악한다 (큐에서 꺼낸 노드가 연결된 방문할 다음 노드의 부모가 되는 구조)- 부모 배열 p를 만들어서 큐 탐색시에 자식과 부모관계 적기 1 -2 -3 (1은 2의 부모 2는 3의 부모..) #include#include#include#includeusing namespace std;//레벨 순회int n,x,y;vectorvt[100002];int p[100002];bool chk[100002];void bfs(){queuepq;pq.push(1); //루트노드chk[1] = true;while (!pq.em..
Tree [TREE의 조건] 1) 연결 그래프이다2) 방향무시하였을때, 싸이클이 존재하지 않는다.3) 트리의 간선 개수는 트리의 정점 개수보다 1작다. TREE를 구현 할때 중요한 것은? - 트리는 재귀적인 구조를 띈다.(DP나 분할 정복의 기법과 굉장히 잘 맞다)-어떤 정점의 서브트리들은 서로 절대영역이 겹치지 않기때문에 각 서브트리에 대한 문제를 풀어 합치면 큰 트리의 문제를 풀 수 있다.(DP 및 분할 정복 ) [TREE의 순회] 1)전위 순회- 모든 정점에 대해서 자기자신을 먼저 방문한 후에 자식들을 방문 (DFS의 성향이 더 강함) 2)중위 순회-자식들 중간에 루트를 방문하는 순회, 왼쪽자식->루트->오른쪽 자식 순서 (차수가 최대 2인 트리에서 주로 사용된다.) 3)후위 순회- 자식들을 모두 방문하고서..
[백준 16235] 나무 재테크 문제: https://www.acmicpc.net/problem/16235 1)문제 분류-시뮬레이션 2)문제해결- 하란대로만 하면 정말 어려운 문제가 아닌데... 1*1에 나무들이 계속 심어지니까 문제를 읽고 고민을 하게된다.. 시간 복잡도랑 메모리가 터지지는않을지..?ㅋㅋ - 내가 구현한 방식은 1*1 에 나무가 계속해서 심어지는 것은 vector에 map[][]을 선언해서 나무들을 심도록한다.봄: 맵을 탐색하면서 나무가 심어진 부분을 보고 , 심어진 나무의 나이대로 정렬을 한다. 나이가 어린나무부터 양분을 먹기때문에, 나이기준 오름차순으로 나무를 정렬을 한 후에 토지의 양분을 섭취하도록한다. 토지의 양분을 먹은 나무는 나이가 +1 되고, 이때 가을에 번식을 할수있다면, 즉 나이가 5의 배수라면 Fal..
[백준 16234]인구 이동 문제 https://www.acmicpc.net/problem/16234 1)문제 분류-시뮬레이션-DFS-BFS 2)문제 해결- 맵을 탐색시, 연합할 수 있는 나라들끼리 묶는다.- 그리고 연합한 나라들끼리 인구이동을 시킨다.- 이때 , chk배열을 둬서 인구이동이 이미 끝난 나라는 건들지 않도록 체크한다.- 종료 조건은 맵을 다 탐색했음에도, 인구이동이 한번이라도, 일어나지 않았다면 종료한다. #include#include#include#include#includeusing namespace std; int N, L, R;int flag;int ans = 0;int chk[52][52];int map[52][52];int xrr[4] = { 0,0,1,-1 };int yrr[4] = { 1,-1,0,0 ..
[백준 16441]아기돼지와 늑대 문제 https://www.acmicpc.net/problem/16441 1)문제 분류-시뮬레이션 2)문제 해결- 방법 1) 늑대의 위치를 큐에 담아 돌릴때 늑대가 움직이는 방향까지 담아서 경로를 3차원으로 체크한다. -방법2)늑대의 위치를 파악하고, 그 지점에서 재귀타고 2차원으로 체크 한다.- 늑대가 한번이라도 왔던 곳이라면 safe[][]에 체크한다.- 문제에서 잘 읽어야 할 부분이 ". 만약 이동한 칸이 빙판이라면 초원을 밟거나 산에 부딪칠 때까지 이동한 방향으로 미끄러집니다. 산에 부딪친 경우 늑대는 빙판 위에 가만히 서있을 수 있고 다시 다른 방향으로 이동할 수 있습니다." > N >> M;for (int i = 0; i < N; i++){for (int j = 0; j < M; j++){sc..
[백준 16954] 움직이는 미로 탈출 문제: https://www.acmicpc.net/problem/16954 1)문제분류-시뮬레이션-BFS 2)문제해결 -1초마다 벽을 이동시켜야 하기 때문에 1초마다 갈 수있는 위치를 큐에 담고, 벽을 이동시킨 후, 담아 놨던 큐로 탐색하며 또 이동.. - 다만 문제에서 잘 읽어야 하는 부분은 "현재 위치에 서 있을 수도 있다" 와 "벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없다." 인 것 같다. 그에 따른 조건 처리를 잘 해줘야 할 듯 싶다.-그리고 구현상 실수할 법한 부분은 벽이 이동할때 행이 큰 것부터 이동 시켜줘야 중복되서 값을 바꾸지 않는다.(예로,연속으로 같은 행에 벽이있다고 치자. 행이 작은 것부터 바꿔서 '#'으로 만들었는데, 행이 큰것의 벽을 이동할때 이전의 바꾼 ..

티스토리툴바