[BOJ] 2644 : 촌수계산(Java)

문제 우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다. 여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오. 입력 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른..

• format_list_bulleted 알고리즘/BOJ
• · 2022. 8. 2.
• textsms

[BOJ] 7569 : 토마토(Java)

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

• format_list_bulleted 알고리즘/BOJ
• · 2022. 8. 2.
• textsms

[Algorithm] BFS : 너비 우선 탐색(Java)

DFS와 함께 가장 널리 사용되는 그래프 탐색 알고리즘인 너비 우선 탐색(Breadth First Search, BFS)에 대해 알아보자. 다익스트라(Dijkstra) 알고리즘이나 최소 스패닝 트리를 찾는 프림(Prim) 알고리즘 등이 BFS를 기반으로 하고 있다. 동작 과정 BFS는 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘이기 때문에 DFS에 비해 매우 직관적이다. 위의 그래프를 보자. a를 탐색의 시작점이라 하면, a에서부터 최소 몇 개의 간선을 지나야 도달할 수 있는가를 기준으로 그래프의 정점들을 나눌 수 있다. 간선 $i$개 지나야 도착할 수 있는 정점의 집합을 $H_i$라고 부르자. 그러면 BFS는 $H_0$에 속한 a를 가장 먼저 방문하고, 그 후 $H_1, H_2$ 그리고 ..

• format_list_bulleted 알고리즘/알고리즘
• · 2022. 8. 2.
• textsms

[Algorithm] 플로이드-워셜(Floyd-Warshall) 알고리즘

다익스트라 VS 플로이드 워셜 다익스트라 알고리즘은 한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 경우 사용할 수 있는 최단 경로 알고리즘이다. 플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용할 수 있는 알고리즘이다. 다익스트라의 경우, 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택한다. 그리고 해당 노드를 거쳐가는 경로를 확인하며, 최단 거리 테이블을 갱신하는 방식으로 동작한다. 그리디 알고리즘에 속한다. 플로이드 워셜의 경우 또한, 단계마다 거쳐 가는 노드를 기준으로 알고리즘을 수행한다. 하지만, 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다는 점이 다익스트라와의 차이점이다. 다이나믹 프로그래밍에 속..

• format_list_bulleted 알고리즘/알고리즘
• · 2022. 7. 6.
• textsms

[Algorithm] 다익스트라(Dijkstra) 알고리즘

다익스트라 알고리즘은 가장 유명한 그래프 알고리즘 중 하나이다. 단일 시작점 최단 경로 알고리즘으로, 시작 정점 $s$에서부터 다른 정점들까지의 최단 거리를 계산한다. 동작 과정 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구하는 알고리즘이다. '음의 간선'이 없을 때 정상적으로 동작한다. 다익스트라 알고리즘은 기본적으로 그리디 알고리즘으로 분류된다. 매번 '가장 비용이 적은 노드'를 선택해 임의의 과정을 반복하기 때문이다. 간략한 원리는 다음과 같다. 출발 노드를 설정한다. 최단 거리 테이블을 초기화한다. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱..

• format_list_bulleted 알고리즘/알고리즘
• · 2022. 3. 25.
• textsms