공부공간

https://www.acmicpc.net/problem/25307 25307번: 시루의 백화점 구경 첫째 줄에 백화점의 세로 길이, 가로 길이, 마네킹과 떨어져야 하는 거리를 의미하는 정수 $N, M, K$가 공백으로 구분되어 주어진다. ($1 \leq N,M \leq 2\,000$, $0 \leq K \leq 4\,000$) 둘째 줄부터 $N$개의 줄 www.acmicpc.net 첫 시작점으로 부터 목적지(2) 까지 갈 수 있는지 확인한다 (bfs) 탐색전 마네킹거리(K, 마네킹 좌표에서 bfs로 k번이동하여 갈수있는곳)를 불가능 표시를 해두고 한번만 BFS를 진행하면 해결된다. import java.io.BufferedReader; import java.io.IOException; import ja..

https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net BFS를 통하여 1 2 3 4 5 6 7 8 0 인 경우에 도달할 수 있는지 확인해주자 ArrayList의 Clone() 메소드를 통하여 현재값과 동일한 객체를 쉽게 만들 수 있다. (방문체크용) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.ArrayList; import ..

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 뱀을 타고 내려가는 것이 이득인 경우가 있을 수 있다. 따라서 모든 경우를 탐색하는 완전탐색 문제이며, bfs로 쉽게 풀린다. 큐에 탐색할때에 를 탐색하면서 현재좌표를 더 낮은 횟수로 올 수 있을때에만 탐색을 진행한다. import java.io.BufferedReader; import java.io.IOException; import java.io...

https://www.acmicpc.net/problem/23747 23747번: 와드 와드를 설치하지는 않았지만, 한별이의 최종 위치의 위, 아래, 왼쪽, 오른쪽 칸은 시야로 확보하고 있다. 지나온 경로를 모두 시야로 확보하지는 않는다. www.acmicpc.net 주어진 움직인 횟수만큼 좌표를 이동시켜주되, w (와드) 인 움직임에서는 BFS를 실행시켜주자, 이 때 WW와 같은 연속된 입력을 방지하기 위해서 . ( 즉 시야가 이전에 밝혀진 ) 곳은 실행 할 필요가 없다. 또한, 경로중에 상하좌우는 밝히지 못하고 최종 좌표에서만 상하좌우 + 최종좌표의 값만 . 로 바꾸어준다. 단순 구현만하면 풀리는 문제이다. package algorithm_2022; import java.io.BufferedReade..

https://www.acmicpc.net/problem/13463 13463번: Brexit The input starts with one line containing four space separated integers C, P, X, and L. These denote the total number of countries (2 ≤ C ≤ 200 000), the number of trading partnerships (1 ≤ P ≤ 300 000), the number of your home country (1 ≤ X www.acmicpc.net 여러개의 행성이 존재하는데, 한 행성이 union을 탈출하면서 해당 행성과 연결되어있는 행성들의 간선개수를 한개씩 줄여준다. 만약 줄여주는 과정에서, 최초..

https://www.acmicpc.net/problem/1584 1584번: 게임 첫째 줄에 위험한 구역의 수 N이 주어진다. 다음 줄부터 N개의 줄에는 X1 Y1 X2 Y2와 같은 형식으로 위험한 구역의 정보가 주어진다. (X1, Y1)은 위험한 구역의 한 모서리이고, (X2, Y2)는 위험한 구역의 www.acmicpc.net 전형적인 0-1 BFS의 문제이다. 죽음의 구역은 못가기때문에, BFS를 돌릴때에 방문한거와 동일하게 처리해준다. 이동할때에, 위험한 구역에 들어가면 1의 가중치가 소요되므로 이경우에는 덱의 맨뒤에 넣고 안전한 구역은 덱의 맨앞에넣어서 탐색을 계속 진행한다. (500,500)에 도달했다면, 최솟값이 보장되기때문에 출력을 진행하면된다. import java.io.Buffered..

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 총 F층짜리 건물에서 S층에서 시작해서 G층으로 가는데 한번의 이동에 +U / -D 만큼의 이동을 할 수 있다. 문제에서 적어도 몇번 가야하는지 물어보았기때문에, 최단거리문제와 동치이고 BFS를 통하여 맨처음 도달했던 횟수를 구하면 출력해준다. 예외적으로 ( +U -D 했을 경우에 건물의 층수 범위를 넘어버린다던가 / 시작할때부터 S==G 인경우는 예외처리해주자 ) import java.io.BufferedR..

https://www.acmicpc.net/problem/15812 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 맵의 모든 1의 개수가 정복되는 최소 시간을 구하는 것이므로 모든경우를 살펴야한다 ( 완전탐색 ) BFS를 이용하여, 1을 만날때마다 카운트를 증가시켜 전체의 1의 개수와 같아질때의 시간을 구한다. 모든경우의 수에서 최소시간이 정답이다 ! import java.io.BufferedReader; import java.io.IOException; import..