문제 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..
문제 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..
11725번: 트리의 부모 찾기 (acmicpc.net) 문제 풀이 입력이 길어 input이 아닌 sys모듈의 stdin.readline 사용 모든 노드의 연결구조를 봐야한다고 생각해서 dfs로 풀긴했지만, bfs로 푸는 것도 오답이 아니라고 생각함. 입력받기는 딕셔너리에 저장. 이때 정점 u와 v가 연결되어있다면 딕셔너리의 키값으로 둘 다 저장함. 이다음 깊이우선탐색을 하는데, 방문여부를 파악하는 동시에 답을 저장함. 이를 위해 딕셔너리 이용. 깊이우선이므로 스택(후입선출) 만들어서 루트노드인 1을 저장. 스택이 빌 때까지 while 반복. 스택에서 pop을 하며 그 노드를 node에 저장. 이 노드가 이미 방문된 노드라면 continue, 아니라면 방문했다는 의미로 visit에 저장. 루트노드인 1은..
https://www.acmicpc.net/problem/12789 12789번: 도키도키 간식드리미 인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두 www.acmicpc.net 문제 문제해석 데큐를 이용하여 순서를 나타내고 대기열 공간은 stack을 활용하여 순서대로 나갈 수 있는지 확인하는 문제이다. 코드 import collections N = int(input()) q = collections.deque(map(int, input().split())) tmp = list() min_value = 1 while q: if q[0] != min_value: tmp.a..
풀이 DFS를 활용하여 그림의 영역을 찾는다. 각각의 1로 이루어진 영역은 하나의 그림을 의미함. 따라서 DFS를 사용하여 연결된 1의 영역을 찾아내고, 각 그림의 넓이를 계산한다. FS 함수는 현재 위치 (x, y)에서 상하좌우로 탐색하며 연결된 영역을 찾아간다. 이때 주의해야 할 점은, 대각선으로는 연결되어 있지 않다고 하였으므로 상하좌우만 고려해야 한다. 만약 (x, y) 위치가 유효하고 아직 방문하지 않았으며, 값이 1이라면, 해당 위치를 방문한 것으로 표시하고 그림의 넓이를 1 증가시킨다. 그리고 이어서 인접한 위치들도 DFS를 호출하여 같은 그림에 속하는지 확인한다. 모든 위치를 순회하면서 그림의 개수와 가장 큰 그림의 넓이를 찾는다. 가장 큰 그림의 넓이를 출력한다. 코드 #include #..
문제 https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 풀이 - deque를 이용하여 BFS로 구현하였다. - 이중 반복문을 통해 탐색을 시작할 위치를 찾고, bfs를 호출한 결과의 제곱을 합한다. - bfs함수가 호출이 되면, 시작 위치를 방문했으므로 0으로 변경하고 q를 생성하여 시작 좌표를 append 하고 반복문을 통해 상하좌우를 확인한다. - 만약 상하좌우의 좌표가 범위를 벗어나지 않고 해당 위치의 병사가 시작 ..
