본문 바로가기

알고리즘 문제147

[알고리즘 문제] 백준1197 - 최소 스패닝 트리 www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 � www.acmicpc.net 최소 스패닝이란 모든 노드가 연결되면서 그 간선들의 합이 최소가 되는 트리입니다. 각 간선의 정보를 가중치가 작은순으로 정렬하고 사이클이 형성되지 않도록 간선을 하나씩 추가해주면 됩니다. 여기서 사이클의 형성여부는 각 노드의 부모값이 같은지를 확인하면 되며 코드상에서는 이를 parent[]로 표현하였습니다. #include #include #include usi.. 2020. 10. 14.
[알고리즘 문제] 백준1987 - 알파벳 www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 전형적인 dfs문제 입니다. 알파벳을 체크와 이미 방문한 곳인지를 검사하면서 탐색하고 이동할때마다 max값을 갱신해주는 방법을 사용하였습니다. #include #include using namespace std; int ans = -1; int width, height; char arr[21][21]; int visited[21][21]; int check[91]; int dx[4] = {0, 1, 0,.. 2020. 10. 14.
[알고리즘 문제] 백준3109 - 빵집 www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 � www.acmicpc.net dfs로 문제를 풀 수 있으며 왼쪽 시작점을 1행 ~ R-1까지 시작점을 바꾸어 가면서 각 시작점에서 출발하여 오른쪽 끝에 도착할 수 있다면 +1을 해줍니다. 여기서 무조건 방문할 때마다 visited[y][x]=1을 해주는데, 이는 y,x위치에서 파이프를 연결할 수 있는지, 없는지 모르지만 어쨋든 방문했다를 표시하기 위함입니다. 다른 시작위치에서 y,x를 간다고 하여도 이미 y,x를 거쳐가는 경우 파이프를 연결할 수 있는.. 2020. 10. 13.
[알고리즘 문제] 백준1038 - 감소하는 수 www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 �� www.acmicpc.net 문제는 bfs를 사용하여 해결할 수 있습니다. 743이라는 이후의 숫자는 마지막숫자보다 작은 숫자들, 7432,7431,7430이 올 수 있습니다. 그리고 arr[j]의 값은 j번째 숫자를 의미하며 que를 순회하면서 마지막 숫자에 그보다 작은 숫자들을 하나씩 붙여가면서 반복합니다. #include #include using namespace std; int main() { int N; ci.. 2020. 10. 13.

티스토리툴바