백준 13424 비밀 모임 Intro Solution 다익스트라 알고리즘을 알고 있다면 쉽게 풀 수 있다. 다익스트라 알고리즘을 이용해 모든 친구들의 이동 비용을 구하여 저장한다. N은 최대 100이므로 K * N은 최대 10000, 친구들의 이동 비용의 합을 도착지마다 구하여 비교하여도 시간 제한을 통과할 수 있다. Code import sys, heapq input = sys.stdin.readline def dijkstra(n, graph, start): cost = [float('inf')] * (n+1) cost[start] = 0 hq = [(cost[start], start)] while hq: t, x = heapq.heappop(hq) if cost[x] != t: continue for..
Koala - 7기/코딩테스트 준비 스터디
https://www.acmicpc.net/problem/13424 13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net 문제분석 분류 그래프 이론, 다익스트라, 플로이드-워셜 문제설명 N개의 방, M개의 비밀통로, K명의 친구들 모임에 참여하는 친구들은 N개의 방 중에서 한 군데씩에 각각 위치해있다. 이들은 항상 처음 위치에서 모임 장소까지의 이동 거리가 가장 짧은 경로만을 이용한다. 모임에 참석하는 친구들의 이동 거리의 총합이 최소가 되는 방을 오늘의 모임 장소로 사용한다. 친구들의 이동 거리의 총합이 최소가 되..
https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제분석 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 N에 있고, 동생은 K에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장..
1504번: 특정한 최단 경로 (acmicpc.net) 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제 해석 방향성이 없는 그래프에서 주어진 2가지의 노드를 거친 1번 노드에서 N번 노드까지의 최단거리를 구하는 문제이다. 만약 경로가 없을 경우, -1를 출력한다. 코드 문제 풀이 3번의 다익스트라를 사용하여 문제를 풀었다. 1번 노드에서 출발하는 다익스트라를 통해 1번 노드 -> 중간노드1, 1번노드 -> 중간노드2의 거리를 구하고 중간노드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 문제 설명 방향성이 있고, 간선에 가중치가 있는 그래프에서 어떤 정점이 특정한 정점 X까지 왕복하는데 가장 거리가 먼지를 찾아내는 문제입니다. 다익스트라 알고리즘으로 해결할 수 있을 것 같습니다. 문제 분석 하지만 문제가 있습니다. 왔던 정점으로 다시 되돌아가야 하는데 방향성이 있기 때문에 되돌아가는 길은 왔던 길과 다릅니다. 이 문제를 해결하기 위해서 모든 정점에서..
https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 분석 수빈이가 동생을 찾는 가장 빠른 시간을 구하는 문제다. 수빈이는 1초에 한 칸씩 앞뒤로 걷거나, 0초에 현재 위치*2의 위치로 순간이동이 가능하다. 다익스트라 알고리즘을 사용하여 풀 수 있다. 코드 #include #include #include #include using namespace std; #define INF 987654321 int n, k..
https://www.acmicpc.net/problem/13907 13907번: 세금 첫 번째 줄에 세 정수 N (2 ≤ N ≤ 1,000), M (1 ≤ M ≤ 30,000), K (0 ≤ K ≤ 30,000)가 주어진다. 각각 도시의 수, 도로의 수, 세금 인상 횟수를 의미한다. 두 번째 줄에는 두 정수 S와 D (1 ≤ S, D ≤ N, S ≠ D www.acmicpc.net 문제분석 세금이 오를 때 마다 간선의 비용이 증가한다. 각각 오를 때 마다의 출발점에서 도착점까지의 최소비용을 출력하라. 코드 import java.io.*; import java.util.*; public class Main { static int n,m,k,s,d; static int[][] mindist; static ..
백준 7576 토마토 Intro Solution 방향을 지정한 리스트를 미리 선언하고, 입력받은 토마토의 위치를 큐를 만들어 집어넣는다. 너비 우선 탐색을 한다. 익지 않은 토마토를 토마토를 익힐 때마다 1을 더하며 그래프를 갱신한다. 그래프에서 가장 큰 값이 토마토를 모두 익히는데 필요한 최소 날짜이다. 익지 않은 토마토 즉 그래프에 0이 있을 경우 -1을 출력한다. Code from collections import deque import sys input = sys.stdin.readline def solve(): m, n = map(int, input().split()) farm = [[*map(int, input().split())] for _ in range(n)] queue = deque()..
4963번: 섬의 개수 (acmicpc.net) 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제 해석 지도가 주어지면 총 섬의 개수를 출력하는 문제이다. 지도에서 서로 인접한 가로, 세로, 대각선의 Land들을 하나의 섬이라고 한다. 코드 문제 풀이 bfs를 이용하여 문제를 풀었다. 처음 v는 인접한 땅을 체크하기 위해 방향벡터를 list로 만들어주었다. 각 테스트케이스마다 while문을 돌면서 반복하며, w, h에 너비와 높이를 저장하고 만약 둘다 0이 입력됐다면 break하여 코드를 종료한다. ..
https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 문제분석 분류 그래프 이론, 다익스트라 문제설명 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 동굴의 크기를 나타내는 정수 N(2 ≤ N ≤ 125)이 주어진다. → 동굴의 크기는 NxN N=0인 입력이 주어지면 전체 입력이 종료된다. [0][0]에서 [N-1][N-1]까지 가는 동안 지나는 칸의 크기만큼 소지금을 잃는다. 잃는 금액을 최소로 ..
https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제분석 한 컴퓨터가 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 문제이다. 코드 def bfs(x): q = deque(); q.append(x) while q: x = q.popleft() for i in arr[x]: if ..
https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net [문제 해석] 본 문제는 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 문제이다. 단, 방문할 수 있는 정점이 여러 개인 경우, 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우에 종료하도록 하는 문제이다. 이때, DFS란 깊이 우선 탐색, BFS는 넓이 우선 탐색을 의미한다. [소스코드] from collections ..
