https://www.acmicpc.net/problem/2852 2852번: NBA 농구 첫째 줄에 골이 들어간 횟수 N(1
분류 전체보기
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 다익스트라 문제이다. 문제에서 버스가 왕복하지 않으므로 양방향이 아닌 단방향으로 그래프에 값을 넣어주면 된다. 시작지점을 입력받아 주어진 출발점을 설정하고 다익스트라 알고리즘을 실행해 주면 된다. 문제에서 '출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.'로 제시해주었으므로 시작지점부터 다른 노드들 사이의 최소가중치를 가지고 있는..
문제: 17608번: 막대기 (acmicpc.net) 17608번: 막대기 아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 www.acmicpc.net 코드 코드 설명 위 문제는 막대기를 차례대로 쌓고, 우측에서 보았을 때 볼 수 있는 막대기의 수를 구하는 것이다. 따라서, 마지막에 쌓은 막대기를 기준으로 총 볼 수 있는 막대기의 개수를 계산을 해야하므로, 스택을 사용을 해주었다. 따라서, 차례대로 입력된 막대기의 높이들을 스택에 넣어주었다. 입력을 끝낸 후, 스택을 돌아보면서, 임의의 변수 max에 현재까지의 막대기의 최고 높이를 저장한 후, 더 큰 높이를 가진 ..
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 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중..
풀이 각 칸마다 해당 칸까지의 최소 소지금을 저장하기 위한 dist 배열을 선언한다. (최대값으로 초기화) 우선순위 큐를 사용하여 최소 칸부터 처리한다. 다익스트라 알고리즘에서 현재 칸에서 다음 칸으로 이동할 때 최소 소지금을 갱신하는 로직을 구현한다. (0, 0) 칸에서 시작. 초기 소지금은 해당 칸의 도둑루피 크기 pq에 (초기 소지금, 시작 칸)을 넣는다. 우선순위 큐에서 하나씩 꺼내면서 해당 칸까지의 최소 소지금을 업데이트한다. 다음 칸으로 이동할 때의 소지금을 갱신하며 다음 칸으로 이동한다. 코드 #include #include #include #include using namespace std; const int INF = INT_MAX; int main() { ios_base::sync_wi..
