문제 백준 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]..

문제 백준 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 ..

문제 백준 14867번 풀이 $ F, E, M $ 연산을 실행하며, 물통에 $ C, D $가 담겨있도록 만드는 최솟값을 구하려면, BFS(너비 우선 탐색)를 사용하면 됩니다. 이미 방문한 정점인지 확인하는 것은 map을 사용하면 쉽게 처리할 수 있습니다. $ F, E, M $ 연산 구현만 유의하면 쉽게 풀 수 있습니다. 소스코드 #include #include #include #include using namespace std; typedef pair pii; unordered_map vis; int ans = -1; int a, b, ta, tb; queue q; void F(int ca, int cb) { if (!vis[a][cb]) { vis[a][cb] = vis[ca][cb] + 1; q.pu..