여행자의 책

https://www.acmicpc.net/problem/2842 2842번: 집배원 한상덕 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 www.acmicpc.net 1. 풀이 사용한 알고리즘은 bfs + 투포인터 이다. 먼저 주어진 지역의 고도 행렬을 중복이 없은 1차원 리스트로 만들어 준 후에 오름차순 정렬해준다. 이 리스트를 heights라고 하겠다. 이후에 초기값이 0인 left, right를 지정해놓고 포인터 값을 변경해가며 heights를 이용해 bfs를 시행하면 되는데 구체적인 로직은 다음과 같다. heights[left:righ..

무작정 큐에 집어넣는게 능사가 아니고 어떤 조건에서 넣어야하는지 항상 판단할 것. 이렇게 풀면 언어의 한계로 통과되지 않음. 아래 다른 분이 푸신 것을 참고해서 풀 것 https://rebas.kr/799 BOJ 16933 · 벽 부수고 이동하기 3 알고리즘 분류 : BFS 벽 부수고 이동하기 시리즈 세 번째 문제이다. 이번에는 이동할 때 낮과 밤이 매번 바뀌고, 낮에만 벽을 부술 수 있다. BOJ 14442번 '벽 부수고 이동하기 2' 문제에서 낮과 밤 설 rebas.kr import sys from collections import deque def solution(): """ 이 풀이가 틀린 풀이는 아니지만 언어의 한계로 시간초과가 난다.""" input = sys.stdin.readline N, ..

import sys """ 내가 두명의 부하 직원에게 연락하라고 시키면 결과적으로 총 걸리는 시간은 둘 중에 가장 큰 값 """ def solution(): input = sys.stdin.readline #입력받는 부분 N = int(input()) bose_info = list(map(int, input().split())) #트리로 만들어 준다. tree = [[] for _ in range(N)] for me, bose in enumerate(bose_info): if bose != -1: tree[bose].append(me) #dp[i] : i번째 노드를 루트로 하는 서브트리에 뉴스를 전달하는데 필요한 최대 시간 dp = [0 for i in range(N)] def dfs(here): tem..

import sys sys.setrecursionlimit(1000000) def solution(): input = sys.stdin.readline N = int(input()) #wolves[i] : i번째 섬에 있는 늑대 수 wolves =[0 for _ in range(N+1)] #sheeps[i] : i번쨰 섬에 있는 양의 수= sheeps = {i:0 for i in range(1, N+1)} #트리 tree =[[] for _ in range(N+1)] for i in range(2, N+1): t, a, p = input().split() a = int(a) p = int(p) if t == "W": wolves[i] = a else: sheeps[i] = a tree[p].append(..

import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) def solution(): n = int(input()) # 노드 100,000개는 log_2(100,000) = 16.xxx # 16개 색깔로 색칠 가능하다. # dp[i][color] : i번째 노드를 color로 색칠했을 때 최소값 dp = [[0] * 16 for i in range(n)] #방문 여부를 체크해준다. visit = [False for i in range(n)] #인접 리스트로 트리의 간선을 기록해준다. tree = [[] for i in range(n)] for i in range(n - 1): a, b = map(int, input().split()) tree..

https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 문제 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들..

문제 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다. 세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 ..

문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. 입력 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다. 그리고 M..