Python/백준
1167_트리의지름
https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 트리구조를 활용한 문제이다. 만약 트리의 어떠한 노드를 무작위로 잡는다고 생각해보자. 그점에서 가장 먼 곳을 잡는다면 한방향으로만 갈수있는 트리방향 특성상 가장 하단이거나 가장 상단일 것이다. 그 점에서 다시 최장거리를 구한다면 결국 트리전체구조의 최장거리를 구할 수 있다. import sys from collections import deque input = sys.stdin.r..
11725_트리의 부모 찾기
https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 트리란 그래프의 일종인데, 중복된 곳에서 한 점으로 올 수 없는 구조이다. 해당 문제에서 트리구조를 찾기위해선, 먼저 연결관계를 모두 기록한 후에 1번 노드를 첫번째 부모로 둔 후, 자식들을 연결해 나가면 해결할 수 있다. import sys sys.setrecursionlimit(100000) input = sys.stdin.readline n = int(input()) tree = [ [] for _ in range(n + 1)] parents =[ 0 f..
11700_플로이드2
https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 해당 유형의 문제는 역시 다익스트라 알고리즘을 활용하고 최단거리 역추적을 이용하면 꽤나 쉽게 풀 수 있다. import sys import heapq input = sys.stdin.readline INF = int(1e9) n= int(input()) m = int(input()) graph = [ [] for _ in range(n+1)] for _ in range(m): s,e,v = m..
11779_최소비용 구하기 2
https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 이전의 다익스트라 알고리즘을 활용하면 풀 수 있다. 이전과 다른점은 어디를 방문했는지 기록을 해둬야 할것이다. 그래서 visited란 배열을 하나 만든 후에, 새로운 노드에 값을 기록할때마다 어느 노드에서 왔는지 기록하도록 하였다. import sys import heapq input = sys.stdin.readline INF = int(1e9) n = int(i..
9019_DSLR
https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net bfs를 활용하면 되는 문제이다. 결국 이전 숨바꼭질 문제들과 비슷하게 풀 수 있다. D,S,L,R 연산을 한번씩 한 후에 dp에 넣어주면서 풀면 된다. 만약 어떠한 연산으로 200이란 수가 나왔다면 그 다음에 200이 나온 경우에는 queue에 추가하지 않는 방식으로 문제를 풀면 될 것이다. 이때 역추적또한 해야하는데, 이전의 데이터를 굳이 넣진 않고 큐 구조에 답을 저장하는 공간을..
13913_숨바꼭질
https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 숨바꼭질의 연장선 문제이다. bfs를 통해서 카운트를 통해 몇초가 걸리는지 걸리는건 해볼 수 있다. 이때 0~100000까지의 배열을 만들어두고 해당하는 초를 새기면서 카운팅을 한다. 그렇다면 이 배열을 기록해나갈때 어느 점에서 나왔는지도 기록을 하면 쉽게 역추적을 할 수 있다. 이배열의 이름을 cnt라고 해보자 예를 들어 5 17인경우 5 10 9 18 17 5..