📙 Algorithm Solving/Java
📙[Algo] 24.09.10 ~ 24.09.16 알고리즘
혜덕hyeduck
2024. 9. 17. 00:59
알고리즘 문제) BOJ 18188.다오의 데이트
문제 요약
- N개의 명령이 주어진다
- 각 명령은 움직일 수 있는 방향 2개가 주어진다
- 다오가 명령에서 주어진 방향 중 하나를 선택해, 한칸씩 이동할 떄, 디지니를 만날 수 있는지를 찾아라
- 블록과 경계밖으로는 이동할 수 없다
시간 제한
- 1초
입력
- 맵크기 세로H와 가로W가 주어진다
- H개의 줄에 맵 정보가 주어진다
- . : 빈칸
- D : 디오 위치
- Z : 디지니 위치
- @ : 블록
- 명령 개수 N개가 주어진다
- 각 명령마다 이동 가능한 방향 2개가 주어진다
- W : 위
- S : 아래
- A : 왼쪽
- D : 오른쪽
- 각 명령마다 이동 가능한 방향 2개가 주어진다
출력
- 만날 수 없다면 NO
- 만날 수 있다면 YES를 출력하고, 어떻게 움직였는지 방향도 출력해라
- 여러 방법이 있다면 아무거나 출력해도 된다.
접근법
- DFS
- 매개변수로 현재위치 cr , cc와 몇번째 명령에 대한 수행인지 나타내는 nth를 매개변수로 갖는 재귀함수 생성
- 이때, 방문체크는 3차원으로 선언 ⇒ 몇 번째 명령에 방문했는지에 따라 방문 체크를 해야한다.
- 늦게 재방문했을 때 그 경로로 디지니를 만날 수도 있으니까
- 방향 정보를 기록하기 위해 log배열에 현재 명령 번호nth인덱스일 때, 방향을 기록했다.
- 만약 현재 위치가 디지니 위치라면 1을 return했고, 재귀호출 부분의 반환값이 0보다 클 경우 무조건 1을 return 하도록했다. ⇒ 경로를 기록하는 log배열이 갱신되는 것을 방지
코드
import java.io.*;
import java.util.*;
public class Main {
static int H, W, N;
static char[][] arr = new char[21][21];
static char[][] cmd = new char[21][2];
static int[] delR = {-1, 1, 0, 0}; // 상 하 좌 우
static int[] delC = {0, 0, -1, 1};
static char[] dir = {'W', 'S', 'A', 'D'};
static boolean[][][] visited = new boolean[21][21][21];
static int[] log = new int[21];
static int sr, sc, er, ec;
static int dfs(int cr, int cc, int nth) {
if (cr == er && cc == ec) {
N = nth - 1;
return 1;
}
if (nth > N) return 0;
int mr, mc, dir;
for (int i = 0; i < 2; i++) {
dir = cmd[nth][i];
mr = cr + delR[dir];
mc = cc + delC[dir];
if (mr < 1 || mc < 1 || H < mr || W < mc
|| arr[mr][mc] == '@' || visited[nth][mr][mc]) continue;
visited[nth][mr][mc] = true;
log[nth] = dir;
if (dfs(mr, mc, nth + 1) > 0) return 1;
visited[nth][mr][mc] = false;
}
return 0;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
H = Integer.parseInt(st.nextToken());
W = Integer.parseInt(st.nextToken());
String input;
for (int i = 1; i <= H; i++) {
input = br.readLine();
for (int j = 1; j <= W; j++) {
arr[i][j] = input.charAt(j - 1);
if (arr[i][j] == 'D') {
sr = i;
sc = j;
} else if (arr[i][j] == 'Z') {
er = i;
ec = j;
}
}
}
N = Integer.parseInt(br.readLine());
char c;
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < 2; j++) {
c = st.nextToken().charAt(0);
if (c == 'W') cmd[i][j] = 0;
else if (c == 'S') cmd[i][j] = 1;
else if (c == 'A') cmd[i][j] = 2;
else if (c == 'D') cmd[i][j] = 3;
}
}
int ret = dfs(sr, sc, 1);
if (ret == 1) {
System.out.println("YES");
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= N; i++) {
sb.append(dir[log[i]]);
}
System.out.println(sb);
} else System.out.println("NO");
}
}
알고리즘 문제) BOJ 3187.양치기 꿍
문제 요약
- 같은 울타리 영역 안의 양들의 숫자가 늑대의 숫자보다 더 많을 경우 늑대가 전부 잡아먹힌다
- 그외의 경우는 양이 전부 잡아먹힌다.
- 빈 공간을 '.'(점)으로 나타내고 울타리를 '#', 늑대를 'v', 양을 'k'라고 나타낸다면 여러분은 몇 마리의 양과 늑대가 살아남을지 계산해라
시간 제한
- 1초
입력
- 입력의 첫 번째 줄에는 각각 영역의 세로와 가로의 길이를 나타내는 두 개의 정수 R, C (3 ≤ R, C ≤ 250)
- 다음 각 R줄에는 C개의 문자가 주어지며 이들은 위에서 설명한 기호를 의미
출력
- 살아남게 되는 양과 늑대의 수를 각각 순서대로 출력
접근법
- 맵을 순회하면서 방문하지 않은 빈칸을 만난 경우 dfs를 돌렸다.
- dfs를 돌면서 울타리안의 공간을 순회하면서, 양과 늑대의 개수를 카운트했다.
- 다 돌고 났을 때 양과 늑대의 개수를 비교하여, 양이 더 많을 경우 살아남은 양의 수에 누적해서 더하고, 그 반대의 경우에는 늑대 수에 누적해서 더했다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int R, C;
static char[][] arr;
static boolean[][] visited;
static int[] delR = {-1, 1, 0, 0};
static int[] delC = {0, 0, -1, 1};
static int wolf, sheep;
static void dfs(int cr, int cc) {
visited[cr][cc] = true;
if (arr[cr][cc] == 'v') wolf++;
else if (arr[cr][cc] == 'k') sheep++;
int mr, mc;
for (int dir = 0; dir < 4; dir++) {
mr = cr + delR[dir];
mc = cc + delC[dir];
if (mr < 0 || mc < 0 || R <= mr || C <= mc
|| arr[mr][mc] == '#' || visited[mr][mc]) continue;
dfs(mr, mc);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
arr = new char[R][C];
visited = new boolean[R][C];
String input;
for (int i = 0; i < R; i++) {
input = br.readLine();
for (int j = 0; j < C; j++) {
arr[i][j] = input.charAt(j);
}
}
int wfSum = 0, spSum = 0;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (visited[i][j] || arr[i][j] == '#') continue;
dfs(i, j);
if (wolf < sheep) {
spSum += sheep;
} else {
wfSum += wolf;
}
wolf = 0;
sheep = 0;
}
}
System.out.println(spSum + " " + wfSum);
}
}
알고리즘 문제) BOJ 29195.Yes or yes
문제 요약
- 1번정점에서 더이상 이동할 수 없는 정점으로 이동하는 경로에서 팬을 만나지 않을 수 있은 경로가 있는지 판단 → 있다면 yes, 불가능하다면 Yes
- 그래프는 무사이클, 유방향그래프
시간 제한
- 1초
입력
- 정점 개수 N, 간선 개수 M
- 1 ≤ N, M ≤ 10만
- M개의 줄에 간선 정보 a, b
- a → b로 가는 경로 존재
- 팬이 존재하는 정점 개수 S
- 1 ≤ S ≤ N
- 각 팬이 존재하는 정점 번호를 의미하는 정수 S개가 주어짐
출력
- 있다면 yes, 불가능하다면 Yes
접근법
- dfs로 더이상 이동할 수 없을 때까지 이동
- → 그 과정에서 팬이 있는 정점을 만난다면 return 1
- 만약 끝까지 이동했는데 없다면 return 0
- 최종적으로 가장 작은 값을 반환할 수 있도록 ret변수를 최솟값으로 갱신
- 이때, dfs 반환값이 0보다 크다면 Yes, 아니라면 yes 출력
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M, S;
static ArrayList<Integer>[] lst;
static boolean[] fans = new boolean[100_010];
static int dfs(int cur) {
if (fans[cur]) return 1;
if (lst[cur].isEmpty()) return 0;
int ret = 1 << 30;
for (Integer nxt : lst[cur]) {
ret = Math.min(ret, dfs(nxt));
}
return ret;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
lst = new ArrayList[N + 1];
for (int i = 0; i < N + 1; i++) {
lst[i] = new ArrayList<>();
}
int a, b;
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
lst[a].add(b);
}
S = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < S; i++) {
fans[Integer.parseInt(st.nextToken())] = true;
}
int ret = dfs(1);
if (ret > 0) System.out.println("Yes");
else System.out.println("yes");
}
}
알고리즘 문제) BOJ 22513. 빠른 오름차순 숫자 탐색
문제 요약
- 보드의 격자에는 -1, 0, 1, 2, 3, 4, 5, 6중 하나의 수가 적혀 있다
- 행 번호는 맨 위 위치가 0이고 아래 방향으로 1씩 증가한다. 열 번호는 맨 왼쪽 위치가 0이고 오른쪽으로 1씩 증가한다
- 맨 왼쪽 위 위치가 (0, 0), 맨 아래 오른쪽 위치가 (4, 4)이다
- -1이 적혀 있는 칸으로는 이동할 수 없고 0, 1, 2, 3, 4, 5, 6이 적혀 있는 칸으로는 이동할 수 있다
- 학생이 현재 위치 (r, c)에서 시작하여 1, 2, 3, 4, 5, 6이 적혀 있는 칸을 순서대로 방문하려고 한다.
- i가 적혀 있는 칸에서 i + 1이 적혀 있는 칸으로 이동할 때 다른 번호가 적힌 칸을 방문해도 된다.(1 ≤ i ≤ 5) 마찬가지로, 현재 위치 (r, c)에서 1이 적혀 있는 칸으로 이동할 때 다른 번호가 적힌 칸을 방문해도 된다.
- 학생이 현재 위치 (r, c)에서 시작하여 1, 2, 3, 4, 5, 6이 적혀 있는 칸을 순서대로 방문하는 최소 이동 횟수를 출력하자.
시간 제한
- 1초
입력
- i번째 줄의 j번째 수는 보드의 (i - 1)번째 행, (j - 1)번째 열에 적혀있는 수를 나타낸다
- 보드의 각 칸에 적혀 있는 수는 -1, 0, 1, 2, 3, 4, 5, 6중 하나이다.
- 1, 2, 3, 4, 5, 6이 적혀 있는 칸이 1개씩 주어진다.
- 다음 줄에 학생의 현재 위치 r, c가 빈칸을 사이에 두고 순서대로 주어진다.
- 0 ≤ r, c ≤ 4
- 학생의 현재 위치 (r, c)에는 0이 적혀 있다.
출력
- 학생이 현재 위치 (r, c)에서 시작하여 1, 2, 3, 4, 5, 6이 적혀 있는 칸을 순서대로 방문하는 최소 이동 횟수를 출력
- 방문할 수 없는 경우 -1을 출력
코드
import java.io.*;
import java.util.*;
public class Main {
static int[][] arr = new int[5][5];
static int[] delR = {-1, 1, 0, 0};
static int[] delC = {0, 0, -1, 1};
static int sr, sc;
static int bfs() {
Queue<int[]> q = new LinkedList<>();
boolean[][][] visited = new boolean[5][5][10];
q.offer(new int[]{sr, sc, 0});
visited[sr][sc][0] = true;
int cr, cc, mr, mc, prv, size, ans = 0;
while (!q.isEmpty()) {
size = q.size();
for (int s = 0; s < size; s++) {
cr = q.peek()[0];
cc = q.peek()[1];
prv = q.poll()[2];
if (prv == 6) return ans;
for (int dir = 0; dir < 4; dir++) {
mr = cr + delR[dir];
mc = cc + delC[dir];
if (mr < 0 || mc < 0 || 5 <= mr || 5 <= mc
|| arr[mr][mc] == -1 || visited[mr][mc][prv]) continue;
if (arr[mr][mc] == prv + 1) {
visited[mr][mc][prv + 1] = true;
q.offer(new int[]{mr, mc, prv + 1});
} else {
visited[mr][mc][prv] = true;
q.offer(new int[]{mr, mc, prv});
}
}
}
ans++;
}
return -1;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
for (int i = 0; i < 5; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < 5; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
st = new StringTokenizer(br.readLine());
sr = Integer.parseInt(st.nextToken());
sc = Integer.parseInt(st.nextToken());
int ret = bfs();
System.out.println(ret);
}
}
알고리즘 문제) BOJ 2829. 아름다운 행렬
문제 요약
- A를 행렬의 주 대각선 성분의 합, B는 또다른 대각선 성분의 합
- 이때, 행렬의 아름다운 정도는 A-B
- N×N크기의 행렬이 주어졌을 때, 아름다운 정도가 가장 큰 부분 행렬을 구하는 프로그램을 작성
- 주 대각선은 행렬의 가장 왼쪽 위에서 시작하는 대각선
시간 제한
- 1초
입력
- 첫째 줄에 행렬의 크기 N이 주어진다. (2 ≤ N ≤ 400)
- 다음 N개의 줄에는 행렬의 성분이 공백으로 구분되어 주어진다. 각 성분은 [-1000,1000] 범위 안에 들어있다.
출력
- 주어진 행렬의 부분 행렬 중 아름다운 정도가 가장 큰 것의 아름다운 정도를 출력
접근법
- a대각선, b대각선의 누적합 배열을 모두 구해준다
- 이후, size가 1~N일때의 부분 행렬들을 모두 탐색하면서 합계의 차이가 가장 큰 값을 찾았다. ⇒ N이 400이므로 N^3이 가능
코드
import java.io.*;
import java.util.*;
public class Main {
static int N;
static int[][] aPrefix;
static int[][] bPrefix;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine().trim());
aPrefix = new int[N + 2][N + 2];
bPrefix = new int[N + 2][N + 2];
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine().trim());
for (int j = 1; j <= N; j++) {
aPrefix[i][j] = Integer.parseInt(st.nextToken());
bPrefix[i][j] = aPrefix[i][j];
}
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
aPrefix[i][j] = aPrefix[i - 1][j - 1] + aPrefix[i][j];
}
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
bPrefix[i][j] = bPrefix[i - 1][j + 1] + bPrefix[i][j];
}
}
int max = Integer.MIN_VALUE, sumA, sumB;
for (int size = 1; size <= N; size++) {
for (int row = size; row <= N; row++) {
for (int col = size; col <= N; col++) {
// size 2, row 3, col 3
sumA = aPrefix[row][col] - aPrefix[row - size][col - size];
sumB = bPrefix[row][col - size + 1] - bPrefix[row - size][col + 1];
max = Math.max(max, sumA - sumB);
}
}
}
System.out.println(max);
}
}
알고리즘 문제) BOJ 20917.사회적 거리 두기
문제 요약
- 각 테스트케이스 별로 n개의 좌석중 s개의 좌석을 선택했을 때, 가장 가까운 거리가 최대가 되는 경우를 찾아라
시간 제한
- 1초
입력
- 테스트케이스의 수 T
- 1 ≤ T ≤ 10
- n s
- 2 ≤ s ≤ n ≤ 20만
- 좌석 후보 위치 x[i]가 n개
- 1 ≤ x[i] ≤ 10억
출력
- 테케별로 가장 가까운 좌석의 거리가 최대가 되는 경우를 찾아라
접근법
- 매개변수탐색 ⇒ 최소가 최대가되는 경우 찾기
- 가장 가까운 거리를 mid값으로 가정한 뒤, 좌석을 순회하면서 두 좌석 거리가 mid보다 크거나 같은경우 카운트
- 카운트한 값이 s보다 크거나 같다면 정답이 될 수 있는 후보로 판단하여 정답변수 갱신 후, 더 큰 값을 찾도록 start를 mid+1로 갱신
- 만약 s보다 작다면, mid값을 너무 크게 가정한 것이므로 end를 mid-1로 갱신
코드
import java.io.*;
import java.util.*;
public class Main {
static int n, s;
static int[] x;
// 11 17 19 21 22 23 28
static int parametricSearch() {
int start = 0, end = x[n - 1] - x[0], mid, cnt, pre, ans = -1;
while (start <= end) {
mid = (start + end) / 2;
cnt = 0;
pre = 0;
for (int i = 1; i < n; i++) {
if (x[i] - x[pre] >= mid){
cnt++;
pre = i;
}
}
cnt++;
if (cnt >= s) {
ans = mid;
start = mid + 1;
} else {
end = mid - 1;
}
}
return ans;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
while (T-- > 0) {
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
s = Integer.parseInt(st.nextToken());
x = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
x[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(x);
int ret = parametricSearch();
sb.append(ret).append("\\n");
}
System.out.println(sb);
}
}