전체 글
-
[BOJ] 연구소 2Algorithm/BOJ 2020. 2. 8. 21:51
[17141] 연구소2 https://www.acmicpc.net/problem/17141 바이러스를 놓을 수 있는 칸(arr[i][j] = 2)에 주어진 M개의 바이러를 놓았을 때 모든 빈 칸(arr[i][j] = 0)에 바이러스를 퍼뜨리는 최소 시간을 구하는 문제 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 칸이다. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다. Solution permutation()을 사용한 BFS 문제 바이러스를 놓을 수 있는 칸의 좌표를 리스트에 모두 담고, permutation() 함수를 돌려 M개의 좌표를 뽑은 후에 BFS로 바이러스를 퍼뜨린다. 소스코드 import java.util.ArrayList; import ..
-
[BOJ] 치킨 배달Algorithm/BOJ 2020. 2. 8. 18:04
[15686] 치킨 배달 https://www.acmicpc.net/problem/15686 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다. 도시의 치킨집 중 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시키려 한다. 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오 Solution permutation()으로 치킨집 중 M개만 골라 치킨거리를 계산한다. 소스코드 import java.util.ArrayList; import java.util.List; import java.util.Scanner; import java.util.StringTokenizer; public class Main { static int n, m, min..
-
[BOJ] 배열 돌리기 4Algorithm/BOJ 2020. 2. 8. 15:24
[17405] 배열 돌리기 4 https://www.acmicpc.net/problem/17406 배열 A와 사용 가능한 회전 연산이 주어졌을 때, 배열 A의 값의 최솟값을 구하는 문제 회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 된다. Solution permuation() 함수를 돌려 회전 순서를 바꿔가면서 simulation한다. 어렵다 T.T 소스코드 import java.util.ArrayList; import java.util.List; import java.util.Scanner; import java.util.StringTokenizer; public class Main { static int n, m, k, min = Integer.MAX_VALUE; static in..
-
[BOJ] DSLRAlgorithm/BOJ 2020. 2. 7. 17:41
[9019] DSLR https://www.acmicpc.net/problem/9019 네 자리 숫자 A와 B가 주어졌을 때 A -> B로 바꾸는 최소 연산 횟수 D : N -> 2*N S : N -> N-1 L : 한 자리씩 왼쪽으로 R : 한 자리씩 오른쪽으로 Solution BFS 풀이방법 이 문제는 어떠한 과정을 거쳐야 하는지를 구해야 한다. Register 객체를 만들어 연산을 했을 때 어떤 과정을 거쳤는지 저장한다. 123에 L 연산을 수행했을 때는 231이 아닌 1230이 계산 결과가 된다. 소스코드 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { public st..
-
[BOJ] 숨바꼭질 2Algorithm/BOJ 2020. 2. 7. 14:35
[12851] 숨바꼭질 2 https://www.acmicpc.net/problem/12851 수빈이의 위치 : N 동생의 위치 : K 동생을 찾는 가장 빠른 시간을 구하는 문제, 그리고 그러한 방법의 개수도 구해야 한다. 수빈이가 할 수 있는 행동 (위치 : X) 1. 걷기 : X + 1 또는 X - 1로 이동(1초) 2. 순간이동 : 2 * X로 이동 (1초) Solution BFS 풀이 방법 경우의 수는 다이나믹 프로그래밍으로 구할 수 있다. cnt[i] = i 까지 가는 방법의 개수 이미 방문을해서 방문을 할 수 없는 경우에 거리가 같으면 방법의 수만 증가해준다. cnt[next] += cnt[cur]; 소스코드 import java.util.LinkedList; import java.util.Q..
-
[BOJ] 숨바꼭질 4Algorithm/BOJ 2020. 2. 6. 21:49
[13913] 숨바꼭질 4 https://www.acmicpc.net/problem/13913 수빈이의 위치 : N 동생의 위치 : K 동생을 찾는 가장 빠른 시간과 이동하는 방법을 구하는 문제 수빈이가 할 수 있는 행동 (위치 : X) 1. 걷기 : X + 1 또는 X - 1로 이동 (1초) 2. 순간이동 : 2 * X로 이동 (1초) Solution BFS 풀이 방법 d[] 배열에 이전 위치를 기억 하면서 걷기, 순간 이동을 한다. 동생을 찾으면 K 위치에서 N 위치까지 역학적으로 경로를 path 리스트에 추가한다. 소스코드 import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.Scanne..
-
[BOJ] 알고스팟카테고리 없음 2020. 2. 5. 18:44
[1261] 알고스팟 https://www.acmicpc.net/problem/1261 미로는 N*M 크기이고, 총 1*1 크기의 방으로 이루어져 있다. 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다. (x,y)에 있을 때, 이동할 수 있는 방은 상, 하, 좌, 우이다. (1,1)에서 (N,M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 문제 Solution 덱을 사용한 BFS 풀이 방법 BFS 탐색을 벽을 부순 횟수에 따라서 나누어서 수행해야 한다. 어차피 벽을 뚫는다와 안 뚫는다로 나누어지기 떄문에, 덱을 사용한다. 벽을 뚫는 경우에는 뒤에, 안 뚫는 경우에는 앞에 추가한다. map[][]에 몇 번 뚫고 지나간 경로인지 횟수를 넣어준다. 소스코드 import ja..
-
[BOJ] 숨바꼭질 3Algorithm/BOJ 2020. 2. 5. 17:36
[13549] 숨바꼭질 3 https://www.acmicpc.net/problem/13549 수빈이의 위치 N 동생의 위치 K 동생을 찾는 가장 빠른 시간을 구하는 문제 수빈이가 할 수 있는 행동(위치 : X) 1. 걷기 : X + 1 또는 X - 1로 이동 (1초) 2. 순간이동 : 2 * X로 이동(0초) Solution 덱을 사용한 BFS 풀이 방법 걷기와 순간이동의 가중치(시간)가 다르기 때문에 덱을 사용해 순간 이동은 덱의 앞에, 걷기는 덱의 뒤에 넣는 방법도 생각해 볼 수 있다. 소스코드 import java.util.Arrays; import java.util.Deque; import java.util.LinkedList; import java.util.Scanner; public clas..