빵똥

https://www.acmicpc.net/problem/15900 15900번: 나무 탈출 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게 www.acmicpc.net 1. 접근 DFS로 접근 시 인접 리스트를 사용하니 O(V + E) == O(500,000 + 499,999) = 1,000,000로 시간 초과 없이 풀 수 있다! 게임의 규칙을 살펴보면 각 말단 노드의 개수 = 말의 수이며 한 턴에 한 번씩 현재 노드의 부모 노드로 이동한다. 또한 게임에서 이기려면 순서가 먼저인 성원이 차례에 마지막 말을 루트로 이동시켜야 한다. 예제 3번을 그림으로 보면 말단..

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 1. 접근 트리의 개념을 코드로 구현해내는 가장 기본적인 문제가 아닐까 싶다. 자료구조 2번에 트리에 대해서 간단히 정리해두었으니 모르는 분은 한 번 보고 오셔도 될 것 같다! https://dhbang.tistory.com/14?category=905670 자료구조 - 2 트리 1. 트리의 개념 트리는 데이터 간의 관계를 나타내는 비선형 자료구조로 특정 조직의 조직도를 대표적인 예로 ..

https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 1. 접근 문제를 풀기 전 시간 복잡도를 구하자! V + E를 T만큼 반복하는데 T는 제시되어 있지 않다! n과 m이 그리 크지 않으니 T도 상식적인 선 안에서 제시되니 일반적인 DFS로 접근해보자! 문제의 조건을 살펴보면 트리의 조건을 제시해주고 해당 조건을 만족하는 개수를 이 형식에 맞춰서 출력해주면 된다. 조건에서 제시된 트리의 기준은 정점이 n이라고 가정했을 때 간선이 n..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 접근 문제를 풀기 전 항상 시간 복잡도를 생각하자! 그래프 탐색에서의 시간 복잡도는 인접 행렬 = V², 인접 리스트 = V + E 이며 이번 문제 포함해 대부분의 문제는 인접 리스트로 접근하니 100,000 + 99,999 = 199,999로 시간 여유는 충분하다! 문제의 조건은 루트를 제외한 각 노드의 부모를 출력하는 것이다. 문제의 예제를 그림으로 그려서 접근해보자. 글로만은 이해가 어려우니 그림을 보며 이해해보자! 탐색을 진행하며 각 정점의 부모가..

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 1. 접근 최대 입력값에 따른 시간 복잡도는 다음과 같다. 칸의 갯수 = H * N * M = 1,000,000로 시간제한안에 여유있게 풀 수있다! 문제의 조건을 살펴보자 익은 토마토 기준으로 상,하,위,아래,좌,우 총 여섯 방향으로 토마토는 익어가며 토마토가 비어있는 칸도 있다. 첫 번째 입력 예제를 그림으로 보면 토마토가 잘 익어가다가 비어있는 칸으로 인해 모두 익지 못..

https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 1. 접근 배열의 최대 크기는 50으로 50 * 50칸을 두 번만 방문하면 되니 약 2,500번만에 풀 수 있는 문제다! 문제의 조건을 살펴보자면 땅은 . * X D S로 총 다섯개로 나눌 수 있으며 물과 고슴도치는 매번 위, 오른쪽, 아래, 왼쪽 총 네 방향으로 이동이 가능하며 물은 벽과 비버굴을 통과할 수 없고 비버는 벽과 물 웅덩이를 통과할 수 없다. 다음과 같은 배치가 있다고 가정했을 때 최단 거리는 ..

https://www.acmicpc.net/problem/5567 5567번: 결혼식 예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대 www.acmicpc.net 1. 접근 상근이의 위치, 즉 1번 정점에서의 거리가 2 이하인 정점의 수만 카운트하면 끝이다! 즉, BFS의 시간복잡도인 O(V + E) = 500 + 10000 이면 풀 수 있다! 자신의 친구, 친구의 친구를 정점과 간선에 비유하면 1과 인접한 정점, 1과 인접한 정점과 인접한 정점(??)까지의 수 이며 2번, 3번, 4번 친구가 초대 대상이 된다. 2. 풀이 변수 세팅 stat..