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

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

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

C++ / 7569 / 토마토 ( 너비 우선 탐색 )

https://www.acmicpc.net/problem/7569문제 요약 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있습니다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관합니다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있습니다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 됩니다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미합니다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정합니다. 철수는 ..

• format_list_bulleted BAEKJOON/BFS
• · 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++ / 11779 / 최소비용 구하기 2 ( 데이크스트라 )

https://www.acmicpc.net/problem/11779문제 요약 n(1≤n≤1,000)개의 도시가 있습니다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있습니다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 합니다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력해야합니다. 항상 시작점에서 도착점으로의 경로가 존재합니다. 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어집니다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어집니다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어집니다. 그리고 그 다..

• format_list_bulleted BAEKJOON/Dijkstra
• · 2025. 4. 22.
• textsms

C++ / 3055 / 탈출 ( 너비 우선 탐색 )

https://www.acmicpc.net/problem/3055문제 요약사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 합니다. 이 숲에는 고슴도치가 한 마리 살고 있습니다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 합니다.티떱숲의 지도는 R행 C열로 이루어져 있습니다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있습니다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있습니다.매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있습니다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장합니다..

• format_list_bulleted BAEKJOON/BFS
• · 2025. 4. 21.
• textsms

C++ / 1261 / 알고스팟 ( 데이크스트라 )

https://www.acmicpc.net/problem/1261문제 요약알고스팟 운영진이 모두 미로에 갇혔습니다. 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없습니다.알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 합니다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방입니다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 입니다. 단, 미로의 밖으로 이동 할 수는 없습니다.벽은 평소에는 이동할 수 없지만, 알고스팟의 ..

• format_list_bulleted BAEKJOON/Dijkstra
• · 2025. 4. 19.
• textsms