𝘚𝘭𝘰𝘸 𝘣𝘶𝘵 𝘴𝘵𝘦𝘢𝘥𝘺

문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 입력 첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다. 출력 첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 ..

문제 다음과 같이 정의된 수열이 있다. D[1] = A D[n] = D[n-1]의 각 자리의 숫자를 P번 곱한 수들의 합 예를 들어 A=57, P=2일 때, 수열 D는 [57, 74(=52+72=25+49), 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, …]이 된다. 그 뒤에는 앞서 나온 수들(57부터가 아니라 58부터)이 반복된다. 이와 같은 수열을 계속 구하다 보면 언젠가 이와 같은 반복수열이 된다. 이때, 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 구하는 프로그램을 작성하시오. 위의 예에서는 [57, 74, 65, 61]의 네 개의 수가 남게 된다. 입력 첫째 줄에 A(1 ≤ A ≤ 9999), P(1 ≤ P ≤ 5)가 주어진다. 출력 첫째 줄에..

문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 출력 첫째 줄에 연결 요소의 개수를 출력한다. 그래프 탐색 알고리즘을 이용하여 푸는 문제. DFS를 사용하여 풀었다. 0번 정점부터 N까지 한번씩 DFS를 실행하되, DFS에서 새로 정점을 방문할 때 마다 c를 1씩 증가시켜 방문한 노드의 수를 세주고, DFS가 끝났을 때 방문한 노드의 수 c가 이전보다 증가했다면 새로운 ..

문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다. ..

'코딩 테스트를 위한 자료 구조와 알고리즘 with C++' 를 참고하여 작성하였습니다. 깊이 우선 탐색(DFS) 보러가기 2.2.3 너비 우선 탐색 ; Breadth-First Search 너비 우선 탐색(BFS)은 시작 정점과 가까운 정점부터 반복적으로 탐색해나가는 방식을 의미한다. 다음과 같은 모양의 그래프가 있다고 가정한다. 0번째 정점을 시작으로 작은 값부터 찾아간다고 가정했을 때, BFS 알고리즘을 적용하면 다음과 같은 순서로 진행된다. 1단계 : 0번 정점 방문 2단계 : 0번 정점과 인접한 정점 중 가장 값이 작은 1번 정점 방문 3단계 : 0번 정점과 인접한 정점 중 방문하지 않았고, 가장 값이 작은 2번 정점 방문 4단계 : 0번 정점과 인접한 정점 중 방문하지 않은 3번 정점 방문 5..

'코딩 테스트를 위한 자료 구조와 알고리즘 with C++' 를 참고하여 작성하였습니다. 더보기 1. 그래프 ; Graph 1.1 개념 그래프 순회 문제를 들어가기 전 짧게 그래프에 대해 설명하자면, 그래프는 정점(vertex)의 집합과 정점들을 서로 잇는 간선(edge)의 집합으로 구성된 자료구조로 연결되어 있는 객체 간의 관계를 표현할 수 있다. 수학적으로는 G = (v는 정점, e는 간선의 집합) 형태로 표현할 수 있다. 간선 방향의 유무에 따라 방향 그래프(directed graph)와 무방향 그래프(undirected graph)로 나눌 수 있고, 간선의 가중치 유무에 따라 가중 그래프(weighted graph)와 비가중 그래프(unweighted graph)로 나눈다. 2. 그래프 순회 문제..