본문 바로가기

알고리즘 문제147

[알고리즘 문제] 백준1012 - 유기농배추 문제는 배추의 상/하/좌/우로 움직일 수 있는 지렁이가 있을 때, 해충으로부터 배추를 보호하는데 필요한 지렁이의 개수를 구하는 문제이다. 설명은 이렇지만, 사실 배추의 군집의 개수를 구하는 문제이다. 이 문제는 dfs를 사용해서 풀 수 있다. 먼저 배열을 모두 검사하다가, 1을 발견하면 그때 부터 탐색을 시작하는데 상/하/좌/우로 1이 있을 떄 까지 탐색하다가 더이상 탐색할 수 없으면 그때 지렁이 수를 하나 증가시키면된다. 코드에서 신기한 점은 탐색을할 때, 배열을 벗어나는지는 검사하지 않는다는 점인데 그 이유는 처음에 배열의 크기를 가로/세로의 크기+1 해주었고, 또 탐색을 할 때, 시작을 0,0가 아닌, 1,1로 시작했기 때문에 절대 배열을 벗어나는 경우가 발생하지 않는다. 또 4방향 탐색을 쉽게 하.. 2019. 7. 17.
[알고리즘 문제] 백준1206 - BFS와 DFS 문제는 간단한데, 그래프와 시작노드가 주어질 때 BFS와 DFS로 구현하는 문제이다. 간선은 [1 2], [1 3], [1 4], [2 4], [3 4]와 같이 표현되며, 이를 사용하여 행렬을 구현하였다. 행렬을 표현할 때, 간선의 방향이 양방향이라고 하였기 떄문에 x,y / y,x에 모두 체크를 해주었다. import java.util.*; public class Main { static boolean[][] graph = new boolean[1001][1001]; static boolean[] visited = new boolean[1001]; static int N; // node static int E; // edge public static void main(String[] args) { Sc.. 2019. 7. 17.
[알고리즘 문제] 백준2667 - 단지번호붙이기 문제 자체는 쉽다. 표에서 1로 생성된 군집의 수와 각각의 군집내에서 1의 숫자를 출력하면 된다. 아이디어는 배열을 반복하면서 가다가 1을 찾으면 그떄부터 탐색을 시작하는데, 이때 dfs와 bfs를 사용하면 된다. 먼저 dfs로 구현을 했고, 이후에 bfs로도 같이 구현을 해보았다. dfs : https://github.com/pyh0414/algorithm/blob/master/dfs/Q2667(dfs).java bfs : https://github.com/pyh0414/algorithm/blob/master/dfs/Q2667(bfs).java 코드에서 좀 특별한 점은, 1. 배열을 선언할 때 N만큼 선언한 게 아니라, N+2만큼 선언 2. dfs,bfs함수를 실행하기 전에 1을 체크하고, 1을 검사하.. 2019. 7. 12.
[알고리즘 문제] 백준1145 - 적어도 대부분의 배수 문제는 어떤 숫자 X(배수)를 구하는 건데 조건은 X입력받은 숫자들로 나누었을 때 나누어떨어지는 숫자가 3개 이상존재하는 X를 구하는 문제이다. 만약 [30 42 70 35 90]숫자를 입력받을 때, 210의 경우는 30,42,70로 나누어 떨어지므로 X가 된다. 방법은 숫자 val을 하나씩 증가하면서 입력받은 배열의 숫자들을 모두 나누어떨어지는지 검사하고 나누어 떨어지는 숫자가 3개 이상이면 val을 출력한다. import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int[] arr = new int[5]; for (int i = 0; i < 5; .. 2019. 7. 5.

티스토리툴바