문제링크:https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 다루는 주제: 다익스트라, 우선순위 큐 # 첫째줄에 N개의 도시 # 둘째줄에 다른 도시로 가는 버스의 개수 M # 셋쨰줄부터 출발 도시 A, 도착 도시 B, 버스 비용 P 정보 입력 # 마지막 줄에 출발 도시 S, 도착 도시 E 입력 # 출발 도시에서 도착 도시로 가는 비용 최소화 최소 비용 출력 # 다익스트라 문제 - 우선순위 큐 사용 - 알아서 최단거..
문제링크:https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 다루는 주제: BFS # N은 도시의 개수 = 노드 개수, M은 도로의 수 = 간선의 개수 1 # 출발하는 도시 X , 최단거리 K # A B는 도시 사이의 단방향 도로 존재 한다는 의미 # 이떄 최단거리 K의 도시가 존재하지 않는다면 -1 출력한다. import sys from collections import d..
문제링크:https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 다루는 주제: DFS # 첫쨰 줄엔 수의 개수 N 과 N-1개수의 연산자 M 입력 # 둘째 줄엔 수열 A 입력 # 셋째줄엔 합이 N-1 인 4개의 정수가 주어지는데 각 + - * / 의 개수가 입력된다. # N개의 수와 N-1의 연산자가 주어졌을떄 만들수있는 식의 최대값과 최소값을 출력하면 된다. # 주의할 점 - 연산자 우선순위를 ..
문제링크:https://www.acmicpc.net/problem/21606 21606번: 아침 산책 1번 정점에서 시작하고 3, 4번 정점에서 끝나는 경로, 3번 정점에서 시작하고 1, 4번 정점에서 끝나는 경로, 4번 정점에서 시작하고 1, 3, 5번 정점에서 끝나는 경로, 5번 정점에서 시작하고 4번 정점 www.acmicpc.net 다루는 주제: DFS # N은 정점의 수 N-1은 간선의 수 # 두번쨰 줄은 길이 N의 문자열 A가 주어지는데 0은 실외 1은 실내 # 세번째 줄부터는 트리의 각 정점을 잇는 간선 정보 import sys sys.setrecursionlimit(10 ** 6) N = int(sys.stdin.readline()) # 정점수 A = [0] + list(map(int, s..
문제링크:https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 다루는 주제: DFS import sys sys.setrecursionlimit(10 ** 6) K = int(sys.stdin.readline()) # dfs def dfs(v, color): visit[v] = color # 방문한 v에 색 할당 for i in tree[v]: if visit[i] == 0: # 안가본곳이면 방문 if dfs(i, -color): pass else: ..
문제링크:https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 다루는 주제: DFS import sys sys.setrecursionlimit(10**6) N = int(sys.stdin.readline()) tree = [[] for _ in range(N + 1)] parent = [0] * (N + 1) for _ in range(N - 1): # 간선의 갯수 = 노드 개수 - 1 a, b = map(int, sys.stdin.readline().split()) tree[a].append(b) tree[b]..
문제링크:https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 다루는 주제: BFS import sys from collections import deque N, M = map(int, sys.stdin.readline().split()) maze = [] # 미로 받기 for i in range(N): maze.append(list(map(int, sys.stdin.readline().strip()))) # 갈수있는 상하좌우 d = [[1, 0], [0, 1], [-1, 0], ..
문제링크:https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 다루는 주제: 그래프 탐색 import sys N = int(sys.stdin.readline()) # N은 컴퓨터의 개수 M = int(sys.stdin.readline()) # M은 간선의 개수 matrix = [[0] * (N + 1) for _ in range(N + 1)] # 영행렬 virus = [0] * (N + 1) count = 0 for _ in range(M): a, b =..
