carsumin devlog 🍀

https://www.acmicpc.net/problem/16956  조건크기 RxC인 목장양은 이동하지 않음, 늑대는 인접한 방향으로 이동 가능울타리를 설치해서 늑대가 양이 있는 칸으로 못가도록 해야 함울타리 개수 제한 없음 풀이 과정양 주변으로1. 늑대-양 인접한가?2. 빈곳 체크해서 울타리 설치 여부 결정 전체 코드import java.io.*;import java.util.*;public class Main{ static int R, C; static char[][] map; static int[] dx = {-1,1,0,0}; static int[] dy = {0,0,-1,1}; public static void main(String[] args) throws ..

https://www.acmicpc.net/problem/3187  조건양 > 늑대 -> 양만 남음 , 늑대 >= 양 -> 늑대만 남음울타리 바깥에는 양 늑대 없음빈공간 있음 필요한 것방문 여부 체크방향 이동 배열 dx, dy울타리, 빈공간, 양늑대 입력 받을 map 배열입력을 공백없이 받음 (charAt 사용) 풀이 과정방문한 적 없고, 울타리가 아니면 BFS 탐색상하좌우 방향 이동하면서 BFS 탐색을 하고 늑대와 양의 개수를 각각 카운트마지막에 최종 늑대와 양의 개수를 비교좌표 형태로 큐에 한번에 담을 수 있음 전체 코드import java.io.*;import java.util.*;public class Main{ static int R,C; //가로C,세로R static char[][]..

https://www.acmicpc.net/problem/2667  풀이이전에 풀었던 영역구하기와 유사한 문제다. (https://marginata.tistory.com/173)영역구하기가 색칠되지 않은 영역의 넓이를 구한것이라면 반대로 단지번호붙이기는 집이 있는곳의 넓이를 구하면 된다.주의할 점은 0001010 이런식으로 공백없이 입력을 받기 때문에 charAt()을 이용해서 한자리씩 char형으로 추출한 뒤에 정수형으로 변환해줘야 한다. 전체 코드import java.io.*;import java.util.*;public class Main{ static int[][] map; //지도 static int[] dx = {1,-1,0,0}; static int[] dy = {0,0,1,..

https://www.acmicpc.net/problem/2583  조건M*N 모눈종이에 K개의 직사각형을 그림K개의 직사각형 내부를 제외한 나머지 부분을 구하는 것분리된 영역 개수, 각 영역의 넓이를 출력(오름차순)필요한 것네 방향으로 움직이면서 탐색하기 위한 dx, dy 배열영역 넓이 결과를 저장할 ArrayList (넓이가 얼마나 나올지 모르기 때문에 가변적인 ArrayList 사용)영역 넓이를 저장할 cnt풀이여기서 M이 높이, N이 너비이다.x,y좌표값은 문제에서 설명하는 것과 다르더라도 그대로 2차원 배열로 나타내도 넓이는 같다.x, y 범위만큼 영역을 1로 채워줌빈 영역을 DFS 탐색  전체 코드import java.io.*;import java.util.*;public class Main{..

https://www.acmicpc.net/problem/2210  조건숫자판의 크기는 5*5인접한 네 방향으로 다섯번 이동 (위, 아래, 오른쪽, 왼쪽)한 번 거쳤던 칸을 다시 거쳐도 됨 = 방문 체크 필요없음서로 다른 여섯 자리 수들의 개수 구하기필요한 것숫자판(grid) 2차원 배열방향 이동을 위한 배열 dx, dy중복을 제거할 수 있는 Set풀이grid 2차원 배열에 값 입력받기각각의 정점(숫자판의 숫자)에서 DFS 탐색하기인접한 네 방향으로 이동int[] dx = {1, -1, 0, 0};int[] dy = {0, 0, 1, -1};/*아래 : dx=1 dy=0 -> 행 번호 1증가 x+1위 : dx=-1 dy=0 -> 행 번호 1감소 x-1오른쪽 : dx=0 dy=1 -> 열 번호 1증가 y+..

https://www.acmicpc.net/problem/1388  '-' 이런 문자가 나오면 -> 이 방향으로 탐색, '|' 이런 문자가 나오면 ↓ 이 방향으로 탐색한다고 생각하면 된다.여기서 어떤 경우에 인접리스트를 사용하고 어떤 경우에 2차원 배열을 사용하는지가 궁금해졌다.* 인접 리스트 사용하는 경우- 정점이 많고, 각 정점에 연결된 간선의 수가 적을 때- 정점 중심의 탐색- 입력이 정점-간선 목록으로 주어질 때* 2차원 배열(그리드, 인접 행렬)을 사용하는 경우- 정점 개수에 비해 간선 개수가 많을 때 ( 예 : N x N 행렬에서 모든 정점이 연결된 완전 그래프 )- 그래프가 2D 격자 형태일 때 ( 예 : 미로찾기, 섬의 개수, 경로 탐색 등 )- 정점 간 연결 여부 체크할 때 ( 예 : 경..

https://www.acmicpc.net/problem/1260   인접리스트를 이용해서 정점의 방문여부를 체크한다. (입력예시)1 2 입력 -> graph = [ [ ], [2], [1], [ ] , [ ] ]1 3 입력 -> graph = [ [ ], [2, 3], [1], [1] , [ ] ]1 4 입력 - > graph = [ [ ], [2, 3, 4], [1], [1] , [1] ]2 4 입력 - > graph = [ [ ], [2, 3, 4], [1, 4], [1] , [1, 2] ]3 4 입력 -> graph = [ [ ], [2, 3, 4], [1, 4], [1, 4] , [1, 2, 3] ]앞에서 풀었던 알고리즘 수업 1,2와 유사함.  풀이import java.io.*;import j..

https://www.acmicpc.net/problem/24479  문제의 조건정점의 수 : N간선의 수 : M시작 정점 : R인접 정점은 오름차순 방문 (24479번 문제)인접 정점은 내림차순 방문 (24480번 문제) 필요한 것ArrayList (이차원 Array는 N*N이라 시간초과 발생함) -> 실제 연결된 간선만 저장하는 ArrayList를 사용하는 것이 메모리 낭비를 줄일 수 있음 - 이차원 배열의 시간 복잡도 : O(N)- 인접 리스트의 시간 복잡도 : O(E), 여기서 E는 간선의 개수. 인접리스트는 간선의 개수와 시간복잡도가 비례한다. 입력받기BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[]..

https://www.acmicpc.net/problem/10451  DFS, BFS 두 가지로 풀 수 있는 문제시간복잡도는 O(N)으로 DFS, BFS 동일하다. DFS (깊이우선탐색) 풀이 문제를 보면 순열을 1부터 세기 때문에 배열의 크기 설정에 주의한다.입력받은 순열을 배열에 넣을 때도 ArrayIndexOutOfBoundsException가 발생하지 않도록 주의한다.순열 배열에 인덱스 1부터 값을 넣기 때문에 그 값에 해당하는 str 배열에서는 index-1을 해줘야한다.노드 방문을 기록할 boolean 타입의 visited 배열을 만들어서 사이클이 중복으로 체크되지 않도록 탐색한다.[ 탐색 과정 ] * n = 1dfs(1)visited[1] = truenextNode = 3 dfs(3) vis..

https://www.acmicpc.net/problem/13241   유클리드 호제법을 이용하여 최소공배수를 구한다.최소공배수 = 두 수의 곱 / 최대공약수 풀이 import java.io.*;import java.util.*;public class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] str = br.readLine().split(" "); long a = Long.parseLong(str[0]); long..