![]()
https://www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 알고리즘 유형 수학 그리디 알고리즘 비트마스킹 문제 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번에 K개의 물병을 옮길 수 있다. 하지만, 지민이는 물을 낭비하기는 싫고, 이동을 한 번보다 많이 하기는 싫다. 따라서, 지민이는 물병의 물을 적절히 재분배해서..
https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 다익스트라 / BFS 문제입니다. 우선순위 큐를 사용하기 위해 Comparable를 사용했고, bfs에서 초기 설정 및 현재 상태 처리를 담당하고, 범위 체크를 하는 함수를 만들어 문제를 해결했습니다. import java.util.*; import java.io.*; public class Main { static int dirX[] = {0, 0, -1, 1}; static ..
문제링크 https://www.acmicpc.net/problem/18223 18223번: 민준이와 마산 그리고 건우 입력의 첫 번째 줄에 정점의 개수 V와 간선의 개수 E, 그리고 건우가 위치한 정점 P가 주어진다. (2 ≤ V ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P ≤ V) 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보 www.acmicpc.net 코드 import heapq input = __import__('sys').stdin.readline v,e,p = map(int,input().split()) graph = [[]*(v+1) for _ in range(v+1)] INF = float('inf') for _ in range(e): a,b,c = map(int,input(..
18352번: 특정 거리의 도시 찾기 (acmicpc.net) 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 단순 다익스트라 문제. 늘 풀던 것과는 다르게 거리정보 없이 그냥 1. graph리스트에 방향정보를 저장. dist리스트에 출발노드에서의 거리를 모두 저장 ~다익스트라 이용 : 힙큐모듈이용 q 리스트 생성. 출발노드 저장. dist에 출발노드는 거리 0 저장. while 반복문으로 q 끝날때까지 돌기! q에서 거리정보가장작은애 p..
문제 https://www.acmicpc.net/problem/17835 17835번: 면접보는 승범이네 첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐 www.acmicpc.net 풀이 도시의 개수만큼 다익스트라 계산하면 대략 10억번의 연산이 수행되어 시간초과가 나온다. 모든 도시에서 면접장으로 갈 수 있는 경로가 항상 있음 -> 면접장에서 도시로 향하는 다익스트라 가능 -> 도시의 연결 정보 입력 시 역방향으로 관계 지정해야 함. (도시: arr / 면접장: targets) 다익스트라에서 탐색 할 도시 리스트 ..
https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 1. 문제풀이 위치가 X일 때 X-1 또는 X+1로 이동하거나 2*X의 위치로 순간이동할 경우 1초가 소모된다. 이동 방법은 3가지임을 알 수 있으며 동일한 시간이 소모됨을 확인할 수 있다. 각 방법에 대하여 시간이 1초가 소모되는 가중치가 동일한 상황이므로 너비 우선 탐색을 시행하여 최단 시간을 구한다. 현재 위치에서 각 방법으로 이동 한 결과를 큐에 넣은 ..
문제 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이 일반적인 다익스트라 문제와 비슷하다. dijkstra() 부분은 큰 차이점이 없다. 양방향이므로 graph에 양쪽 모두 추가해주고, 이 부분을 주의해야한다. d1 = dijkstra(1) d2 = dijkstra(v1) d3 = dijkstra(v2) res = min(d1[v1]+d2[v2]+d3[N], d1[v2]+d3[v1]+d2[N])..
![]()
문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net Algorithm 다익스트라 문제이다. 문제에서 버스가 왕복하지 않으므로 양방향이 아닌 단방향으로 그래프에 값을 넣어주면 된다. 시작지점을 입력받아 주어진 출발점을 설정하고 다익스트라 알고리즘을 실행해 주면 된다. 문제에서 '출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.'로 제시해주었으므로 시작지점부터 다른 노드들 사이의 최소가중치를 가지고 있는..
![]()
Problem Solution 변수 및 데이터 입력**: `n`, `m`, `k`를 입력받는다. `INF`라는 상수를 사용하여 무한을 나타낸다. `INT_MAX`는 C++에서 정수의 최댓값을 나타내는 상수이다. `graph`는 정점과 간선 정보를 저장하는 2차원 벡터이고 `distance`는 각 정점까지의 최단 거리를 저장하는 배열로 초기값은 모두 무한으로 설정한다. `m`번 만큼 간선 정보를 입력받아 `graph`에 저장하고 각 간선은 시작 노드, 도착 노드, 비용으로 구성한다. `dijkstra` 함수를 정의한다. 우선순위 큐 `q`를 사용하여 노드까지의 최단 거리를 기준으로 노드를 선택하고 알고리즘을 통해 시작 노드로부터 각 노드까지의 최단 거리를 계산하고 `distance` 배열에 저장한다. `d..
![]()
https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 알고리즘 분류 구현 시뮬레이션 문제 로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 방은 N*M 크기의 직사각형으로 나타낼 수 있으며, 1*1 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중..
![]()
문제 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 풀이 특정 시작점에서 다른 모든 정점으로 가는 최단 거리를 구해주는 알고리즘인 다익스트라를 이용하여 구현한다. 문제는 다른 모든 마을에서 파티가 열리는 마을로 가는 최단 거리와 돌아오는 최단 거리를 구해야 한다. - 각 마을로 돌아가는 최단 거리는 특정 시작점이 파티가 열리는 마을이므로 입력받은 대로 다익스트라를 적용하면 된다. - 그러나 모든 정점(각 마을)에..
문제링크 https://www.acmicpc.net/problem/24445 24445번: 알고리즘 수업 - 너비 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 코드 from collections import deque input = __import__('sys').stdin.readline n,m,r = map(int,input().split()) graph = [[] for _ in range(n+1)] for _ in range(m): a,b = map(int,inpu..
