📙 Algorithm Solving/Java
📙[Algo] 24.03.29~24.03.31 알고리즘
혜덕hyeduck
2024. 3. 31. 20:49
알고리즘 문제) BOJ 1967. 숨바꼭질
문제 요약
- 시작 점 i에서 1초 후 (1) i - 1, i + 1 이동 가능, (2) i * 2로 이동 가능 할 때 도착 지점 까지 가려면 최소 몇 번 이동?
시간 제한
- 2초
입력
- 시작 위치 N과 도 위치 K
- N(0 ≤ N ≤ 100,000)
- K(0 ≤ K ≤ 100,000)
출력
- 도착 지점까지 가려면 최소 몇 번 이동?
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, K;
static boolean[] visited;
static Queue<Integer> q = new LinkedList<>();
static int dist;
static int[] mul = {1, 1, 2};
static int[] add = {-1, 1, 0};
static void bfs(int node) {
q.offer(node);
visited[node] = true;
int cur, nxt, size;
while (!q.isEmpty()) {
size = q.size();
for (int i = 0; i < size; i++) {
cur = q.poll();
if (cur == K) {
System.out.println(dist);
return;
}
/*
if (0 <= cur - 1 && !visited[cur - 1]) {
}
if (cur + 1 <= 100000 && !visited[cur + 1]) {
q.offer(cur + 1);
visited[cur + 1] = true;
}
if (2 * cur <= 100000 && !visited[2 * cur]) {
q.offer(2 * cur);
visited[2 * cur] = true;
}
연산이 많아지면 번거로우니까 형태를 맞춰준다.
1 * cur - 1
1 * cur + 1
2 * cur + 0
곱해지는 수, 더해지는 수를 배열로 만들고 활용
int[] mul = {1, 1, 2};
int[] add = {-1, 1, 0};
*/
for (int j = 0; j < 3; j++) {
nxt = mul[j] * cur + add[j];
if (nxt < 0 || 500000 < nxt || visited[nxt]) continue;
q.offer(nxt);
visited[nxt] = true;
}
}
dist++;
}
}
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());
K = Integer.parseInt(st.nextToken());
visited = new boolean[500010];
bfs(N);
}
}
알고리즘 문제) BOJ 2178. 미로 탐색
문제 요약
- N*M 크기 미로가 있음
- 미로에서 1은 이동할 수 있는 칸, 0은 이동할 수 없는 칸
- (1,1)에서 (N,M)위치로 이동할 때 지나야 하는 최소 칸 수 구하기
- 서로 인접한 칸으로만 이동 가능
시간 제한
- 1초
입력
- 첫째 줄 : 두 정수 N, M
- 2≤N,M≤100
- N개의 줄에 M개의 정수로 미로가 주어짐(공백X)
출력
- 지나야 하는 최소 칸 수 출력
- 무조건 도착지로 이동하는 경우만 입력으로 주어짐
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static int[][] map;
static boolean[][] visited;
static int[] delR = {-1, 1, 0, 0};
static int[] delC = {0, 0, -1, 1};
static int dist;
static void bfs(int row, int col) {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{row, col});
visited[row][col] = true;
int cRow, cCol, mRow, mCol, size;
while (!q.isEmpty()) {
size = q.size();
for (int i = 0; i < size; i++) {
cRow = q.peek()[0];
cCol = q.poll()[1];
if (cRow == N - 1 && cCol == M - 1) return;
for (int dir = 0; dir < 4; dir++) {
mRow = cRow + delR[dir];
mCol = cCol + delC[dir];
if (mRow < 0 || mCol < 0 || N <= mRow || M <= mCol
|| visited[mRow][mCol] || map[mRow][mCol] == 0) continue;
q.offer(new int[]{mRow, mCol});
visited[mRow][mCol] = true;
}
}
dist++;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
String input;
for (int i = 0; i < N; i++) {
input = br.readLine();
for (int j = 0; j < M; j++) {
map[i][j] = input.charAt(j) - '0';
}
}
visited = new boolean[N][M];
bfs(0, 0);
bw.write(String.valueOf(dist + 1));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 1753. 최단경로
문제 요약
- 방향 그래프가 주어지고, 다른 모든 정점으로의 최단 경로 구하기
- 모든 간선의 가중치는 10이하 자연수
시간 제한
- 1초
입력
- 첫째 줄 : 정점 개수 V, 간선 개수 E
- 1≤V≤2만
- 1≤E≤30만
- 둘째 줄 : 시작 정점의 번호 K
- 1≤K≤V
- 셋째 줄부터 E개 줄에 걸쳐 세 개의 정수 u v w가 주어짐
- u에서 v로가는 가중치 w인 간선이 존재
- u≠v, w는 10이하 자연수
- 서로 다른 두 정점 사이에 여러 간선이 존재할 수 있음
- u에서 v로가는 가중치 w인 간선이 존재
출력
- V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값 출력
- 시작점 자신은 0으로 출력
- 경로가 존재하지 않은 경우 INF를 출력
접근법
- 다익스트라 알고리즘 사용
- 두 간선 사이 여러 경로가 존재 → 우선순위큐 사용하면 가장 작은 애를 꺼내줌
코드
import java.io.*;
import java.util.*;
public class Main {
static int V, E, K;
static ArrayList<Node>[] list;
static boolean[] visited;
static int[] dist;
static class Node implements Comparable<Node> {
int to;
int weight;
Node(int to, int weight) {
this.to = to;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
return this.weight - o.weight;
}
}
static void dijk(int start) {
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(start, dist[0]));
int cur, nxt, nw;
while (!pq.isEmpty()) {
cur = pq.poll().to;
if (visited[cur]) continue;
visited[cur] = true;
for (Node node : list[cur]) {
nxt = node.to;
nw = dist[cur] + node.weight;
dist[nxt] = Math.min(dist[nxt], nw);
pq.offer(new Node(nxt, dist[nxt]));
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
K = Integer.parseInt(br.readLine());
list = new ArrayList[V + 1];
for (int i = 0; i < V + 1; i++) {
list[i] = new ArrayList<>();
}
int v1, v2, w;
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
v1 = Integer.parseInt(st.nextToken());
v2 = Integer.parseInt(st.nextToken());
w = Integer.parseInt(st.nextToken());
// 방향 그래프이니까 하나만
list[v1].add(new Node(v2, w));
}
dist = new int[V + 1];
Arrays.fill(dist, 300010);
dist[K] = 0;
visited = new boolean[V + 1];
dijk(K);
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= V; i++) {
if (dist[i] == 300010) sb.append("INF\\n");
else sb.append(dist[i]+"\\n");
}
bw.write(String.valueOf(sb));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 2589. 보물섬
문제 요약
- 각 칸은 L(육지), W(바다)로 표시
- 상하좌우로 이동 가능
- 한 칸 이동할 때 1시간
- 보물은 서로 최단 거리로 이동할 때 가장 긴 시간이 걸리는 육지 두 곳에 묻혀 있음
- 보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 프로그램을 작성
시간 제한
- 1초
입력
- 첫째 줄 : 지도 세로, 가로 크기
- 각각 50이하
- 둘째 줄부터 지도가 주어짐
출력
- 보물이 묻혀 있는 두 곳 사이를 최단 거리로 이동하는 시간을 출력
접근법
최단거리 → bfs
지도 크기가 최대 50*50 이니까 2500
육지인 노드 하나씩 bfs돌리면서 가장 거리가 먼 육지 노드까지 길이를 구한다 ⇒ 이때 최댓값으로 갱신
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static char[][] map;
static boolean[][] visited;
static Queue<int[]> q = new LinkedList<>();
static int[] delR = {-1, 1, 0, 0};
static int[] delC = {0, 0, -1, 1};
static int answer;
static void bfs(int row, int col) {
q.offer(new int[]{row, col});
visited[row][col] = true;
int cRow, cCol, mRow, mCol, size, dist = 0;
while (!q.isEmpty()) {
size = q.size();
for (int i = 0; i < size; i++) {
cRow = q.peek()[0];
cCol = q.poll()[1];
for (int dir = 0; dir < 4; dir++) {
mRow = cRow + delR[dir];
mCol = cCol + delC[dir];
if (mRow < 0 || mCol < 0 || N <= mRow || M <= mCol
|| visited[mRow][mCol] || map[mRow][mCol] == 'W') continue;
q.offer(new int[]{mRow, mCol});
visited[mRow][mCol] = true;
}
}
dist++;
}
answer = Math.max(answer, dist - 1);
}
static void initVisited() {
for (int i = 0; i < N; i++) {
Arrays.fill(visited[i], false);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new char[N][M];
String input;
for (int i = 0; i < N; i++) {
input = br.readLine();
for (int j = 0; j < M; j++) {
map[i][j] = input.charAt(j);
}
}
visited = new boolean[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 'L') {
initVisited();
bfs(i, j);
}
}
}
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 13913. 숨바꼭질 4
문제 요약
- 수빈이는 현재 점 N에 위치, 동생은 점 K에 위치
- 수빈이가 현재 위치가 X라면 1초 후에 X-1, X+1, 2*X위치로 이동 가능
- 수빈이와 동생위치가 주어졌을 때 동생을 찾을 수 있는 가장 빠른 시간은?
시간 제한
- 2초
입력
- 수빈이가 있는 위치 N, 동생이 있는 위치 K가 주어짐
- N(0 ≤ N ≤ 100,000)
- K(0 ≤ K ≤ 100,000)
출력
- 수빈이가 동생을 찾는 가장 빠른 시간 출력
- 어떻게 이동해야 하는지 공백으로 구분해 출력
접근법
- 경로 기록하기
- 5 → 6 , 4, 10
- 4 → 3, 8
- 8 → 16
- 16 → 17
- 방향 그래프를 만든다 생각하면?
- arr[5][6] = 1, arr[5][4] = 1, ….. arr[16][17] = 1
- 나중에 경로를 찾을 때 → stack에 담는다 (LIFO)
int end = 17;
while(true){
if (end == 5) stack.add(i);break;
for (int i=0 ; i≤100000 ≤ i++)
if(arr[i][end] == 1){
stack.add(i);
end = i;
break;
}
}
}
⇒ 이렇게하면 메모리 초과
그냥 그전 노드가 누구였는지 기록 하기
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, K;
static boolean[] visited;
static int[] mul = {1, 1, 2};
static int[] add = {1, -1, 0};
static int[] log;
static int dist;
static void bfs(int start) {
Queue<Integer> q = new LinkedList<>();
q.offer(start);
visited[start] = true;
int cur, nxt, size;
while (!q.isEmpty()) {
size = q.size();
for (int i = 0; i < size; i++) {
cur = q.poll();
if (cur == K) return;
// 1*cur+1
// 1*cur-1
// 2*cur+0
for (int j = 0; j < 3; j++) {
nxt = mul[j] * cur + add[j];
if (**nxt < 0 || 200000 < nxt** || visited[nxt] ) continue;
q.offer(nxt);
visited[nxt] = true;
log[nxt] = cur;
}
}
dist++;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
visited = new boolean[200010];
log = new int[200010];
bfs(N);
Stack<Integer> stack = new Stack<>();
int end = K;
while (true) {
stack.add(end);
if (end == N) break;
end = log[end];
}
StringBuilder sb = new StringBuilder();
for (int i = 0, size = stack.size(); i < size; i++) {
sb.append(stack.pop() + " ");
}
bw.write(dist + "\\n" + sb);
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 7576. 토마토
문제 요약
- M*N
- 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다
- 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향
- 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수
시간 제한
- 1초
입력
- M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다.
- 단, 2 ≤ M,N ≤ 1,000
- 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다
- 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸
출력
- 토마토가 모두 익을 때까지의 최소 날짜를 출력
- 토마토가 모두 익지는 못하는 상황이면 -1을 출력
코드
import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int N, M;
static int[][] map;
static Queue<int[]> q = new LinkedList<>();
static int[] delR = {-1, 1, 0, 0};
static int[] delC = {0, 0, -1, 1};
static boolean[][] visited;
static int tomatoCnt;
static int cnt;
static int answer;
static void bfs() {
int crow, ccol, mrow, mcol, size;
while (!q.isEmpty()) {
size = q.size();
for (int i = 0; i < size; i++) {
crow = q.peek()[0];
ccol = q.poll()[1];
cnt++;
for (int dir = 0; dir < 4; dir++) {
mrow = crow + delR[dir];
mcol = ccol + delC[dir];
if (mrow < 0 || mcol < 0 || N <= mrow || M <= mcol
|| visited[mrow][mcol] || map[mrow][mcol] == -1) continue;
visited[mrow][mcol] = true;
q.offer(new int[]{mrow, mcol});
}
}
answer++;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
map = new int[N][M];
visited = new boolean[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if (map[i][j] != -1){
tomatoCnt++;
if (map[i][j] == 1){
q.offer(new int[]{i, j});
visited[i][j] = true;
}
}
}
}
bfs();
if (cnt == tomatoCnt) bw.write(String.valueOf(answer - 1));
else bw.write(String.valueOf(-1));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 1261. 알고스팟
문제 요약
- 미로는 NM 크기이며, 총 11 크기 방으로 이루어져 있다
- 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1)
- 여러 명이 다른 방에 있을 수는 없다.
- 현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지
시간 제한
- 1초
입력
- 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)
- 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1
- 0은 빈 방을 의미하고, 1은 벽
- (1, 1)과 (N, M)은 항상 뚫려있다.
출력
- 알고스팟 운영진이 (N, M)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 출력
코드
import java.io.*;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
static int N, M;
static int[][] map;
static int[] delR = {-1, 1, 0, 0};
static int[] delC = {0, 0, -1, 1};
static boolean[][] visited;
static class Node implements Comparable<Node>{
int row;
int col;
int wall;
Node(int row, int col, int wall) {
this.row = row;
this.col = col;
this.wall = wall;
}
@Override
public int compareTo(Node o) {
return this.wall - o.wall;
}
}
static void bfs(int row, int col) {
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(row, col, 0));
visited[row][col] = true;
Node node;
int crow, ccol, mrow, mcol;
while (!pq.isEmpty()) {
node = pq.poll();
crow = node.row;
ccol = node.col;
if (crow == N - 1 && ccol == M - 1) {
System.out.println(node.wall);
return;
}
for (int dir = 0; dir < 4; dir++) {
mrow = crow + delR[dir];
mcol = ccol + delC[dir];
if (mrow < 0 || mcol < 0 || N <= mrow || M <= mcol || visited[mrow][mcol]) continue;
visited[mrow][mcol] = true;
if (map[mrow][mcol] == 1) pq.offer(new Node(mrow, mcol, node.wall + 1));
else pq.offer(new Node(mrow, mcol, node.wall));
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
map = new int[N][M];
String input;
for (int i = 0; i < N; i++) {
input = br.readLine();
for (int j = 0; j < M; j++) {
map[i][j] = input.charAt(j) - '0';
}
}
visited = new boolean[N][M];
bfs(0, 0);
br.close();
}
}
알고리즘 문제) BOJ 1389. 케빈 베이컨의 6단계 법칙
문제 요약
- BOJ 유저의 수와 친구 관계가 입력으로 주어졌을 때, 케빈 베이컨의 수가 가장 작은 사람을 구하는 프로그램을 작성
- 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산
- 케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합
시간 제한
- 2초
입력
- 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)
- M개의 줄에는 친구 관계
- 친구 관계는 중복되어 들어올 수도 있으며,
- 친구가 한 명도 없는 사람은 없다.
- 모든 사람은 친구 관계로 연결되어져 있다
출력
- 케빈 베이컨의 수가 가장 작은 사람을 출력
- 여러 명일 경우에는 번호가 가장 작은 사람을 출력
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static ArrayList<Integer>[] list;
static Queue<Integer> q = new LinkedList<>();
static boolean[] visited;
static int bfs(int node, int target) {
q.offer(node);
visited[node] = true;
int cur, size, cnt = 0;
while (!q.isEmpty()) {
size = q.size();
for (int i = 0; i < size; i++) {
cur = q.poll();
if (cur == target){
q.clear();
return cnt;
}
for (Integer nxt : list[cur]) {
if (visited[nxt]) continue;
q.offer(nxt);
visited[nxt] = true;
}
}
cnt++;
}
return -1;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
list = new ArrayList[N + 1];
for (int i = 0; i < N + 1; i++) {
list[i] = new ArrayList<>();
}
int node1, node2;
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
node1 = Integer.parseInt(st.nextToken());
node2 = Integer.parseInt(st.nextToken());
list[node1].add(node2);
list[node2].add(node1);
}
visited = new boolean[N + 1];
int sum, ansNode = 0, ansSum = 1 << 30, tmp;
for (int i = 1; i <= N; i++) {
sum = 0;
for (int j = 1; j <= N; j++) {
if (i == j) continue;
tmp = bfs(i, j);
sum += tmp;
Arrays.fill(visited, false);
}
if (ansSum > sum) {
ansSum = sum;
ansNode = i;
}
}
bw.write(String.valueOf(ansNode));
bw.flush();
bw.close();
br.close();
}
}