공부공간

https://www.acmicpc.net/problem/3109 3109번: 빵집 문제 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 중에, 가스비가 제일 크다는 것을 알게되었다. 따라서 원웅이는 근처 빵집의 가스관에 몰래 파이프를 설치해 훔쳐서 사용하기로 했다. 빵집이 있는 곳은 R*C 격자로 표현할 수 있다. 첫째 열은 근처 빵집의 가스관이고, 마지막 열은 원웅이의 빵집이다. 원웅이는 가스관과 빵 www.acmicpc.net 벽을 피해 파이프를 연결하는 문제이다. 파이프는 현재좌표에서 x 좌표는 +1 / y 좌표는 -1,0,1인 지점에 벽이 아닌공간에 설치할 수 ..

https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있는 곳으로는 이동할 수 없다. 시작점과 도착점은 항상 평지이다. W와 H는 1이상 200이하의 자연수이고, K는 0이상 30이하의 정수이다. www.acmicpc.net 원숭이는 K번 말처럼 움직일 수 있다. 왼쪽 끝 ( 0,0 ) 에서 시작하여 ( y-1 , x-1 )까지 이동하면서 최단경로를 구하는 문제이다. 최단경로를 구하기위해 BFS알고리즘을 사용했으나.. 방문처리가 상당히 까다로웠다. 먼저, 말처럼이동..

https://www.acmicpc.net/problem/14868 14868번: 문명 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 세계의 크기를 나타내는 정수 N(2 ≤ N ≤ 2,000)과 문명 발상지의 수 K(1 ≤ K ≤ 100,000)가 주어진다. 다음 K줄에는 한 줄에 하나씩 문명 발상지에 해당하는 정사각형의 위치 (x,y)를 나타내는 두 자연수 x와 y가 주어진다. (1 ≤ x,y ≤N) www.acmicpc.net 문명을 bfs로 전파하면서 전체 문명의수가 한개가되는 즉, union-find를 동시에 수행하면서 전체 root가 1개가 되는 시점을 찾으면된다. 편향트리가 될수있기에, rank를 이용하여서 꼭 정리를 해주어야한다. 이러한 disjoint set과 완전탐색이 결합된 문제..

https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 문제 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 가로로 R, 세로로 C만큼의 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다. 호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다. 아래에는 세 가지 예가 있다. ...XXXXXX..XX.XXX ....XXXX.......XX www.acmicpc.net 최적화의 끝.. 문제는 쉽다. MAP에서 . 와 인접한 X는 매초 녹는다. 녹으면서 생기는 .을 통하여 두개의 L이 만날수있는지 물어..

https://www.acmicpc.net/problem/1238 1238번: 파티 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다. 이 도로들은 단방향이기 때 www.acmicpc.net N개의 노드에서 다시 자신의 노드로 돌아오는데에 최댓값을 구하는 문제이다. 1~N까지 Floye-Warshall 알고리즘을 통해 최단경로를 ..

https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다. (1, 1)과 (N, M)은 항상 뚫려있다. www.acmicpc.net 1,1에서 N,M으로 벽을 최단개수로 부수면서 진행할 때에 몇개의 벽을 부수어야하는지 체크해주는 문제이다. 우선순위큐에 현재좌표와 몇개의 벽을 부수고 왔는지 체크해주면서 벽의 개수가 적은 순으로 정렬시킨다. 방문체크를 해주면서 1,1에서 N,M까지 진행시킨다. 4분탐색시에 갈곳이 1 이면 한개의 벽을 부수어야하므로 현재의 BR..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다. 그리고 M+3째 줄에는 우리가 구하고자 하는 구간 www.acmicpc.net Dijkstra알고리즘의 기본적인 형태이다. 특정 A번째에서 B번째까지의 최단 경로를 구하기위해서 정수배열에 A번째에서 각 인덱스..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다. 그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 www.acmicpc.net MST를 구현하는 알고리즘에는 3가지가 있다. 1. Prim Algorithm 2. Kruskal Algorithm 3. Soll..