![]()
https://www.acmicpc.net/problem/29687 29687번: Игра Два игрока играют в новую настольную игру. На поле для игры есть города и дороги между ними, причем дороги между разными городами могут имет www.acmicpc.net 알고리즘 분류 그래프 이론 데이크스트라 최단 경로 문제 Два игрока играют в новую настольную игру. На поле для игры есть города и дороги между ними, причем дороги между разными городами могут иметь различную длину. ..
![]()
문제 https://www.acmicpc.net/problem/21736 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net 풀이 너비우선탐색(BFS)을 통해 만날 수 있는 사람이 몇 명인지 찾아낸다. 현재 위치인 'I'의 좌표를 찾고 이를 시작점으로 하여 q에 삽입한다. q의 첫 번째 값을 pop 하고, 이 값의 상하좌우를 확인하여 표의 범위를 벗어나지 않고 벽('X')이 아니라면 (+방문하지 않았다면), 해당 위치를 방문했다고 값을 변경하고, q에 삽입한다. 이때 P라면 ans를 증가시킨다. 위 과..
문제 https://www.acmicpc.net/problem/5464 5464번: 주차장 시내 주차장은 1부터 N까지 번호가 매겨진 N개의 주차 공간을 가지고 있다. 이 주차장은 매일 아침 모든 주차 공간이 비어 있는 상태에서 영업을 시작하며, 하룻동안 다음과 같은 방식으로 운영 www.acmicpc.net 코드 #include #include #include #include #include #include using namespace std; int main() { int n = 0; int m = 0; int parkingsp[101]={0}; int parkingcst[101]; queue car; vector carwt; cin >> n >> m; for (int i = 0; i > parkin..
![]()
문제 설명 주어진 조건대로 따라가는 문제이다. 차가 들어오면 빈 공간에 주차시키고, 빈 공간이 없다면 대기열에 넣는다. 차가 나간다면 요금을 부과하고 대기열에 있는 차를 주차시킨다. 코드 #include using namespace std; struct park { int cost; bool isPark; }; struct car { int weight; int pnum; }; int N, M, answer; vector parks(101, { 0, false }); vector cars(2001, { 0, 0 }); queue waitlist; // 빈자리 찾거나 없으면 -1 반환 int CheckEmptyPark() { for (int i = 1; i 0) { parks[pnum].isPark = t..
![]()
5464번: 주차장 (acmicpc.net) 5464번: 주차장 시내 주차장은 1부터 N까지 번호가 매겨진 N개의 주차 공간을 가지고 있다. 이 주차장은 매일 아침 모든 주차 공간이 비어 있는 상태에서 영업을 시작하며, 하룻동안 다음과 같은 방식으로 운영 www.acmicpc.net 코드 n,m=map(int,input().split()) #주차공간n 차량m Rs=[0] #단위무게당요금 i 번쨰 Wk=[0] #차량의 무게 i 번째 for _ in range(n): Rs.append(int(input())) for _ in range(m): Wk.append(int(input())) I=[] #차 오고가는거 큐 for _ in range(2*m): I.append(int(input())) money=0 #..
![]()
문제 https://www.acmicpc.net/problem/1446 풀이 다익스트라로 구현하였다. 0에서 시작하여 d까지 가야 하므로 거리를 모두 노드로 볼 수 있다. for문을 통해 graph를 최소거리가 1로 초기화하고, 최단 거리 테이블을 무한으로 초기화한다. 입력받은 지름길을 graph에 추가한다. (만약 종료지점이 d보다 크다면 추가하지 않는다.) 다익스트라 함수 구현 - 시작 노드로 가기 위한 최단 경로를 0으로 설정하여 큐에 삽입한다. - q가 존재한다면, 가장 최단 거리가 짧은 노드에 대한 정보를 heappop 한다. (dist, now) - dist가 now까지의 최단 거리보다 길다면, continue 한다. - dist가 더 짧다면, 현재 노드의 지름길들을 반복문으로 탐색한다. - ..
문제 https://www.acmicpc.net/problem/3036 3036번: 링 출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다. www.acmicpc.net 코드 #include #include #include #include #include using namespace std; int main() { int n = 0; cin >> n; vector arr; int srr[100][2]; int a = 0; for (int i = 0; i > a; arr.push_back(a); } int b = 0; for (int i = 0; i
![]()
5972번: 택배 배송 (acmicpc.net) 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 코드 import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) import heapq n,m=map(int,input().split()) #노드1에서 n까지최단거리구하기 #di={} graph=[[] for _ in range(n+1)] for _ in range(m): a,b,c=map(int,input().split()) #a와b를잇는길의비용:c graph[..
![]()
https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 알고리즘 분류 그래프 이론 데이크스트라 최단 경로 문제 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주인공, 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다. [0][0]번 칸이기도 하다. 왜 이런 곳에 들..
![]()
문제 https://www.acmicpc.net/problem/5972 풀이 택배 배송 문제, 여물을 헛간인 1에서 헛간 N으로 배달하는 것은 여러가지 그래프를 활용하여 풀 수 있다. 그중 가는 길의 길이는 고려하지 않으므로, 다익스트라를 활용하여 풀 수 있다. 입력에 대한 그래프를 구성하는 과정에서, 해당 문제는 간선에 대해 방향을 따지지 않는 무향 그래프 이므로, 입력 시에 양쪽 출력 노드에 대해 값을 추가해주어야 한다. 코드 import heapq INF = int(1e9) N,M = map(int, input().split()) graph = [[] * (N+1) for _ in range(N+1)] distance = [INF] * (N+1) for _ in range(M): a,b,c = ma..
0. 문제 https://www.acmicpc.net/problem/29687 29687번: Игра Два игрока играют в новую настольную игру. На поле для игры есть города и дороги между ними, причем дороги между разными городами могут имет www.acmicpc.net 문제 해석 두 명의 플레이어가 새로운 보드 게임을 하고 있습니다. 경기장에는 도시와 도시 사이에 도로가 있으며, 도시마다 도로의 길이가 다를 수 있습니다. 또한 두 도시 사이의 도로 길이가 x라면 이 도로에는 (x-1)개의 마을이 연속적으로 있으므로 도시에서 도로의 가장 바깥쪽 마을로, 이 마을에서 이웃 마을로 갈 수 있습니다...
![]()
https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 문제 코드 import sys from collections import deque def bfs(x): queue = deque([x]) visited[x] = 1 cnt = 0 while queue: queue.popleft() for i in range(1, n + 1): if visited[i] == 0: queue.append(i) visited[i]..
