문제 백준 16940번 풀이 이러한 트리를 BFS, 너비 우선 탐색으로 순회한 결과가 올바른 것인지 아닌지 출력해야 합니다. 이 과정이 올바르다면, 아래의 조건을 만족할 것입니다. 1) 각 노드의 깊이는 오름차순 형태이다. 2) 부모 노드가 들어온 순서대로 자식 노드들 간의 순서가 결정된다. 2번째 조건이 말로 하면 어려우니, 아래 예제를 참고해주세요. 위 예제 사진에서는, 깊이가 0(루트 노드)인 노드는 1, 깊이가 1인 노드는 2와 3, 깊이가 2인 노드는 4입니다. 아래와 같이 순회했다고 가정합시다. 1 2 3 4 1번째 조건에서, 각 노드들의 깊이를 배열로 나타내면, [0, 1, 1, 2]이므로 오름차순을 만족합니다. 2번째 조건에서, 각 노드들의 부모 노드는 (루트 노드 제외) [1, 1, 2]..

문제 백준 15918번 풀이 $ x $와 $ y $ 자리가 주어집니다. 문제에서 같은 수는 수열에서 "2번" 나오고, 같은 수 ($ k $) 사이의 원소 개수가 $ k $가 된다고 하였으니, $ x $와 $ y $ 자리에 넣을 수는 $ y - x + 1 $로 정해집니다. 나머지 수를 채우는 방법은 dfs를 사용하여 $ 2^(12) $만큼 돌면서 조건에 맞게 수열을 채워주면 됩니다. 시간 복잡도는 $ O(2^N) $이 됩니다. 소스코드 #include #define all(v) v.begin(), v.end() using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pii; typedef pair pll;..

문제 백준 5578번 풀이 다른 문제와 달리 연결된 얼음의 넓이를 구하는 것이 아니라, 한번씩만 지나갈 수 있을 때 얼음을 최대한 많이 밟아야 합니다. 맵의 크기가 작기 때문에 DFS를 사용하여 완전 탐색을 하면 됩니다. 소스코드 #include using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pii; typedef pair pll; typedef vector vi; typedef vector vl; int mp[91][91], ans, n, m; vector mv = { {-1, 0}, {0, -1}, {1, 0}, {0, 1}, }; int dfs(int x, int y) { int c = 0..

문제 백준 2146번 풀이 임의의 섬 하나를 지정합니다. 그리고, 그 섬의 테두리를 계속 한칸씩 늘려줍니다. 테스트케이스의 경우, 왼쪽 윗 섬을 잡고, 길이를 1씩 늘리면 위와 같은 모양이 됩니다. 계속해서 길이를 2로 늘려주면, 위와 같이 됩니다. 마지막으로 길이가 3이 되면, 다른 섬과 닿게 됩니다. 위 과정은 너비 우선 탐색, BFS로 해결할 수 있습니다. 이러한 과정을 나머지 섬에도 모두 해주면서 답을 갱신해주면 됩니다. 소스코드 #include using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pii; typedef pair pll; typedef vector vi; typedef vect..

문제 백준 1595번 풀이 임의의 정점 $ v_{0} $에서 가장 먼 정점 $ v_{1} $을 DFS 또는 BFS로 찾아줍니다. 다시 정점 $ v_{1} $에서 가장 먼 정점 $ v_{2} $를 찾아줍니다. 도시 $ v_{1} $과 $ v_{2} $의 거리가 정답이 됩니다. 자료형에 유의해줘야하는데, int를 사용하면 12%에서, long long을 사용하면 100%에서 틀렸습니다. unsigned long long 박으니 풀렸습니다. 소스코드 #include using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pii; typedef pair pll; typedef pair pull; typedef ..

문제 백준 9997번 풀이 모든 경우의 수를 고려하더라도 시간 복잡도가 $ O(2^N) $ 이므로 시간 내에 해결할 수 있습니다. 그러나, 비트 연산자를 이용해서 탐색하는 경우 시간 복잡도가 $ O(N 2^N) $ 이므로 TLE가 나기 때문에, dfs를 구현하여 풀어야 됩니다. a부터 z를 사용하였는지 체크하는 것은 OR 비트 연산을 사용하여 빠르게 처리할 수 있습니다. 소스코드 #include using namespace std; typedef long long ll; int n; vector vec; int solve(int sz, int vis) { if (sz == n) { if (vis == (1 > n; for (int i = 0; i > s..