해커를 꿈꾸는 개발자

파이썬 / BOJ 백준 / 1932번 정수 삼각형 - dp

https://www.acmicpc.net/problem/1932

문제

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

풀이

1. dp로 풀 수 있는 문제입니다.
2. 위 층의 값들을 아래층의 값에 합산해 갈 수 있는데, 합산하는데 3가지 case가 있습니다.
3. 첫번째 케이스는 j = 0일 경우 아래층의 값은 바로 위층의 값을 가져와 합산합니다.
dp[i][j] + dp[i - 1][j]
4. 두번째 케이스는 i = j일 경우 아래층의 값은 왼쪽 대각선 위층의 값을 가져와 합산합니다.
dp[i][j] = dp[i][j] + dp[i - 1][j - 1]
5. 세번째 케이스는 나머지 조건일 경우 아래층의 값은 바로 위층의 값과 왼쪽 대각선 위층의 값중 큰 값을 가져와 합산합니다.
dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + dp[i][j]

6. 마지막으로 맨 아래층의 값 중 가장 큰값을 출력합니다.

전체코드

n = int(input())
dp = []
for i in range(n):
    dp.append(list(map(int, input().split())))
k = 2
for i in range(1, n):
    for j in range(k):
        if j == 0:
            dp[i][j] = dp[i][j] + dp[i - 1][j]
        elif i == j:
            dp[i][j] = dp[i][j] + dp[i - 1][j - 1]
        else:
            dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + dp[i][j]
    k += 1
print(max(dp[n - 1]))

알고리즘 : 최소 스패닝 트리(Minimum Spanning Tree) - 크루스칼 알고리즘 구현하기

최소 스패닝 트리는 스패닝 트리 중에서 사용된 간선들의 가중치 합이 최소인 트리를 말합니다. 

최소 스패닝 트리를 만들기 위한 조건은 아래와 같습니다. 

- 본래의 그래피의 모든 노드를 포함해야 합니다. 

- 간선의 가중치의 합이 최소여야 합니다. 

- 모든 노드가 서로 연결되어 있어야 합니다. 

- Cycle이 존재하지 말아야 합니다. 

최소 스패닝 트리를 구하기 위한 대표적인 알고리즘이 2가지가 있습니다. 

첫번째는 크루스칼 알고리즘(Kruskal Algorithm)이며, 두번째는 프림 알고리즘(Prim Algorithm)입니다. 

이번 시간에는 크루스칼 알고리즘에 대해 알아보겠습니다. 

크루스칼 동작 원리

1) 모든 간선들의 가중치를 오름차순으로 정렬합니다 

2) 가중치가 가장 작은 간선부터 선택합니다. 

3) 선택한 간선이 사이클을 만들지 않는다면, 두 개의 노드를 연결합니다. 

4) 모든 노드를 연결할 때까지 1) ~ 3)의 과정을 반복합니다. 

크루스칼 동작 과정

아래와 같은 그래프가 있다고 가정합니다. 

노드는 1부터 7까지 있고, 모든 노드가 연결되지 않은 독립된 상태입니다. 

노드 1과 노드 2의 간선의 가중치는 3입니다. 

다른 모든 연결된 간선도 가중치를 가지고 있습니다. 

이 그래프를 크루스칼 알고리즘을 이용하여, 최소 스패닝 트리를 찾아보도록 하겠습니다. 

먼저 Parent 배열을 만들고, 각 주소에 각 노드로 초기화합니다. Parent 배열은 각 연결된 부분의 가장 상단의 부모가 공통인지를 검사하여, 각 노드가 연결되어 있는지, 독립하여 존재하는지 검사하기 위해 사용됩니다. (즉, 두 노드를 연결할 때, Cycle이 발생하지 않도록 검사하기 위해 필요합니다.)

모든 간선은 가중치의 값을 오름차순으로 정렬하도록 합니다. 

간선의 가중치가 가장 낮은 {2} 와 {3}을 연결시킵니다. 

To의 Parent는 From의 최 상위의 부모로 지정합니다. 

그러면 [2]에는 From인 3이 부모가 됩니다. 

이러한 과정을 반복합니다. 

노드 1과 노드 2를 연결하면 사이클이 발생하여 연결되지 못합니다. 또한 노드 5와 노드 6, 노드 5와 노드 4도 동일하게 사이클을 발생시키기 때문에 연결되지 못합니다. 

크루스칼 알고리즘을 동작시키면, 아래와 같이 최소 스패닝 트리가 구해지고, 

최소 비용의 값은 14가 됩니다. 

크루스칼 구현

#include <iostream>
#include <ctime>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <sstream>
#include <queue>
#include <stack>
#include <list>
using namespace std;


// 간선의 정보를 나타낼 구조체를 정의합니다. 
struct Edge {
    int from, to, weight;
    Edge(int f, int t, int w) {
        from = f;
        to = t;
        weight = w;
    }
};

vector<Edge> v; // 모든 간선의 정보를 담음
int N; // 노드의 수
int M; // 간선의 수 
int result = 0; // 최소 스패닝 트리의 모든 가중치의 합
int parent[100001]; // Parent 배열

// 입력정보
void inputData() {
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int f, t, w;
        cin >> f >> t >> w;
        v.push_back(Edge(f, t, w));
    }
}

void printV() {
    for (int i = 0; i < M; i++) {
        cout << v[i].from << " " << v[i].to << " => " << v[i].weight << '\n';
    }
}

// 가중치 오름차순으로 정렬하기 위한 compare 함수
bool comp(const Edge& e1, const Edge& e2) {
    return e1.weight < e2.weight;
}

// 최상위의 부모노드를 구합니다. 
int getParent(int x) {
    if (x == parent[x]) return x;
    else
        return parent[x] = getParent(parent[x]);
}

// 두 노드를 연결합니다. 
void Union(int x, int y)
{
    x = getParent(x);
    y = getParent(y);

    if (x == y) return ; // 두 노드의 최상위 부모가 동일한지 검사합니다.
    parent[y] = x;
}

// 사이클을 이루는지 확인합니다.
bool isCycle(int x, int y) {
    x = getParent(x);
    y = getParent(y);

    if (x == y)
        return true;

    return false; 
}


void solve() {
    sort(v.begin(), v.end(), comp); // 가중치 오름차순으로 간선을 정렬합니다. 
    
    for (int i = 1; i <= N; i++) parent[i] = i; // 우선 parent 배열에 각 노드로 초기합니다.

	// 두 노드를 연결하였을 때, 사이클을 이루지 않는다면, 두 노드를 연결시킵니다. 
    for (int i = 0; i < v.size(); i++) {
        if (isCycle(v[i].from, v[i].to) == false) {
           // cout << " Union : " << v[i].from << " " << v[i].to << " w : " << v[i].weight << '\n';
            Union(v[i].from, v[i].to);

            result += v[i].weight; // 가중치의 모든 합을 구합니다. 
        }
    }
}

void printData() {
    cout << result;
}

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    inputData();
    solve();
    printData();

    return 0;
}

파이썬 / BOJ 백준 알고리즘 / 11724번 연결 요소의 개수 - DFS

문제 풀이 

이번 문제는 dfs 또는 bfs로 풀 수 있는 문제인데, dfs로 풀어보도록 하겠습니다. 

각 노드를 생성하고, 간선을 연결하여 graph를 만들어 줍니다. 

그리고 각 노드에 대하여 dfs를 진행하도록 하는데, 각 노드에 방문하였다면 skip합니다.

이때 노드에 방문하지 않고, dfs를 진행하도록 하면 count를 올려줍니다. 

dfs를 진행하면서 각 노드에 대하여 visited[node]에 방문했는지 여부를 설정합니다.  

이 동작을 반복하다보면 count를 구할 수 있게 됩니다. 

전체 코드

import sys
sys.setrecursionlimit(10000)

def dfs(index, V, G):
	V[index] = 1
	for i in range(1, N+1):
		if index == i or V[i] == 1 or G[index][i] == 0:
			continue
		dfs(i, V, G)

MAX = 1001
# 입력
N, M = map(int, input().split(' '))

# 변수 설정
graph = [[0] * (MAX+1) for i in range(MAX+1)]
visited = [0] * (MAX+1)
cnt = 0

for i in range(M):
	u, v = map(int, sys.stdin.readline().split())

	## graph u->v, v->u 설정
	graph[u][v] = 1
	graph[v][u] = 1

for i in range(1, N+1):
	if visited[i] == 0:
		dfs(i, visited, graph)
		cnt += 1


print(cnt)

파이썬 / 백준 알고리즘 / 1260번 DFS와 BFS 문제 및 풀이

https://www.acmicpc.net/problem/1260

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오.
단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다.
한 간선이 여러 번 주어질 수도 있는데, 간선이 하나만 있는 것으로 생각하면 된다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력 및 출력

문제 풀이

너비우선탐색(BFS, Breadth First Search)와 깊이우선탐색(Depth First Search)의 전형적인 기초 문제입니다. 이 두 알고리즘은 그래프를 탐색하기 위한 알고리즘으로 모든 정점을 탐색하기 위해 사용됩니다.

DFS는 한 경로로 탐색하다가 특정 상황에서 최대한 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 경로로 탐색하는 방식이고,(스택의 방식을 이용함, 스택은 기본 동작이라 스택 자료 구조를 이용할 필요는 없음)
BFS는 갈림길에 연결되어 있는 모든 경로를 한번씩 탐색한 뒤 다시 연결되어 있는 모든 경로를 넓게 탐색하는 방식입니다. (자료 구조 큐 또는 덱 구조를 이용해야 함)

예를 들어 아래와 같은 그래프에서 DFS 동작은 다음과 같습니다. 
1) 정점 1에서부터 검색 시작
2) 1에 연결된 정점 2,3,4 중 가장 작은 수인 2(방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야 된다고 기입 됨)를 방문
3) 2에 연결된 정점 4를 방문
4) 4에 연결된 정점 3을 방문
5) 더이상 방문할 정점이 없으므로 종료
- 결국 1->2->4->3 순으로 방문하게 됩니다

예를 들어 아래와 같은 그래프에서 BFS 동작은 다음과 같습니다.
1) 정점 1에서부터 검색 시작 
2) 정점 1과 연결된 2를 검색(방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야 된다고 기입 됨) 
3) 정점 1과 연결된 3을 검색(방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야 된다고 기입 됨) 
4) 정점 1과 연결된 4를 검색 
- 결국 1->2->3->4 순으로 방문하게 됩니다. 

전체 코드

from collections import deque

def dfs(v):
    print(v, end=' ')
    visit[v] = 1
    for i in range(1, n + 1):
        if visit[i] == 0 and adj[v][i] == 1:
            dfs(i)

def bfs(v):
    queue = deque()
    visit[v] = 1
    queue.append(v)

    while (queue):
        v = queue.popleft()
        print(v, end=' ')
        for i in range(1, n + 1):
            if visit[i] == 0 and adj[v][i] == 1:
                queue.append(i)
                visit[i] = 1

#입력 n : 정점의 개수, m : 간선의 개수, v : 탐색을 시작할 정점의 번호
n, m, v = map(int, input().split())
adj = [[0] * (n + 1) for i in range(n + 1)]
visit = [0 for i in range(n + 1)]
for i in range(m):
    x, y = map(int, input().split())
    adj[x][y] = 1
    adj[y][x] = 1

#출력
dfs(v)
print()

visit = [0 for i in range(n + 1)]
bfs(v)