공부공간

https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 매번 가장큰 size를 가진 일반 블록을 찾기위해 NXN을 탐색한다. (사이즈가 같은경우는 무지개 블록이, 무지개블록이 같은경우는 대표블록의 Y,X값을 참조) 해당 블록이 그룹이 되는 조건을 BFS를 진행하며 확인해준다. ( size가 1이면 그룹이 될 수 없다 ) 또한, 점수를 획득할 그룹이 지정되면 반시계반향으로 돌리는 로직과 ( y,x -> 한변의 길이-x,y ) 중력을 받아서 아래로 내..

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/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..

https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 미로의 방문체크를 N^2 으로하면서 최단경로를 Deque로 계산한다. package algorithm; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.StringTokenizer; public class 미로만들기 { public static void m..