본문 바로가기
728x90

그래프

 (6)
[백준] 1167번 트리의 지름 [Python] 트리의 지름을 구하는 문제 N개의 노드에 대해서 각 노드마다 한 줄에 그 노드, 연결된 노드1, 거리1, 노드2, 거리2, ... -1 이런 구조로 정보가 주어진다. 예$)$ 3, 1, 2, 4, 3, -1 >>> 3과 1은 거리가 2; 3과 4는 거리가 3; -1: 끝 의미 트리$($tree$)$는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다. 이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경..
[백준] 1967번 트리의 지름 [Python] 트리$($tree$)$는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다. 이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다. 더보기 문제 입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해서 출력하는 프로그램을 작성하시오. 아래와 같은 트리가 주어진다면 트리의 지름은 45가 된다. 트리의 노드는 1부터 n까지 번호가 매겨져 있다...
[프로그래머스] Lv.3 등산코스 정하기 [Python] N 개의 지점은 출입구, 쉼터, 산봉우리로 이루어져 있습니다. 이 문제에서 출입구에서 산봉우리를 하나만 거처 다시 출입구로 돌아가는 경로를 등산코스라고 정의합니다. 한 등산코스 내 각 지점 사이의 최대 소요시간을 해당 등산코스의 intensity라고 합니다. 가능한 등산코스 중 최소 intensity와 그 값을 갖는 산봉우리를 구하는 문제 더보기 문제 설명 XX산은 n개의 지점으로 이루어져 있습니다. 각 지점은 1부터 n까지 번호가 붙어있으며, 출입구, 쉼터, 혹은 산봉우리입니다. 각 지점은 양방향 통행이 가능한 등산로로 연결되어 있으며, 서로 다른 지점을 이동할 때 이 등산로를 이용해야 합니다. 이때, 등산로별로 이동하는데 일정 시간이 소요됩니다. 등산코스는 방문할 지점 번호들을 순서대로 나열하여 표현..
[백준] 13549번 숨바꼭질 3 [Python] - 데이크스트라 N을 아래 연산을 통해서 K로 바꾸는 데 걸리는 시간을 구하는 문제 연산 : 소요 시간 +1 또는 -1 : 1초 x2$($2배$)$ : 0초 더보기 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N$(0 ≤ N ≤ 100,000)$에 있고, 동생은 점 K$(0 ≤ K ≤ 100,000)$에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 ..
[백준] 12865번 이진 검색 트리 [Python] 이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 문제 이진 검색 트리 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 전위 순회: 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리 후위 순회: 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트 더보기 문제 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 전위 순회 $($루트-왼쪽-오른..
[백준] 11724번 연결 요소의 개수 [Python] - 그래프 이론 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 문제 더보기 문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 출력 첫째 줄에 연결 요소의 개수를 출력한다. https://www.acmicpc.net/problem/11724 1번 노드부터 시작해서 연결된 번호의 노드를 훑고 지나면서 각 노드랑 연결된 노드까지도 살펴봅니다..

티스토리툴바