C++ / 1967 / 트리의 지름 ( 깊이 우선 탐색 )

https://www.acmicpc.net/problem/1967문제 요약트리(tree)는 사이클이 없는 무방향 그래프입니다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 됩니다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것입니다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 됩니다.이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 합니다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말합니다.입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해서 출력하는 프로그램을 작성해야 합니다. 아래와 같은 트리가 주어진다면 트리의 지름..

• format_list_bulleted BAEKJOON/DFS
• · 2025. 4. 24.
• textsms

C++ / 1707 / 이분 그래프 ( 깊이 우선 탐색 )

https://www.acmicpc.net/problem/1707문제 요약 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부릅니다.그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성해야합니다. 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어집니다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있습니다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는..

• format_list_bulleted BAEKJOON/DFS
• · 2025. 4. 24.
• textsms

C++ / 2638 / 치즈 ( 깊이 우선 탐색 )

https://www.acmicpc.net/problem/2638문제 요약 N×M의 모눈종이 위에 아주 얇은 치즈가 과 같이 표시되어 있습니다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수 입니다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹습니다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버립니다. 따라서 아래 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라집니다. 와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정합니다. 그러므 로 이 공간..

• format_list_bulleted BAEKJOON/DFS
• · 2025. 4. 17.
• textsms

C++ / 2573 / 빙산 ( 깊이 우선 탐색 )

https://www.acmicpc.net/problem/2573문제 요약 지구 온난화로 인하여 북극의 빙산이 녹고 있습니다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 합니다. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장됩니다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장됩니다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각합니다.빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어듭니다다. 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않습니다. 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있습니다. 따라서 그림 1..

• format_list_bulleted BAEKJOON/DFS
• · 2025. 2. 28.
• textsms

C++ / 1303 / 전쟁 - 전투 ( 깊이 우선 탐색 )

https://www.acmicpc.net/problem/1303문제 요약전쟁은 어느덧 전면전이 시작되었습니다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었습니다. 그러나 당신의 병사들은 흰색 옷을 입고, 적국의 병사들은 파란색 옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있습니다. 문제는 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실입니다.N명이 뭉쳐있을 때는 N2의 위력을 낼 수 있다. 과연 지금 난전의 상황에서는 누가 승리할 것인가? 단, 같은 팀의 병사들이 대각선으로만 인접한 경우는 뭉쳐 있다고 보지 않습니다.  첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (..

• format_list_bulleted BAEKJOON/DFS
• · 2025. 2. 4.
• textsms

C++ / 1189 / 컴백홈 ( 백트래킹 )

https://www.acmicpc.net/problem/1189문제 요약 한수는 캠프를 마치고 집에 돌아가려 합니다. 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있습니다. 그리고 한수는 집에 돌아가는 방법이 다양합니다. 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않습니다. 위 예제는 한수가 집에 돌아갈 수 있는 모든 경우를 나타낸 것입니다. T로 표시된 부분은 가지 못하는 부분입니다. 문제는 R x C 맵에 못가는 부분이 주어지고 거리 K가 주어지면 한수가 집까지도 도착하는 경우 중 거리가 K인 가짓수를 구하는 것입니다. 문제 풀이1. 지도의 크기 r과  c를 입력 받고 목표 깊이인 c를 입력 받습니다.2. 캐릭터 2차원 벡터로 지도를 그려주고 dfs 탐색을 r-1 * 0 부터 깊이..

• format_list_bulleted BAEKJOON/Backtracking
• · 2025. 1. 11.
• textsms