📙 Algorithm Solving/Java
📙[Algo] 24.04.03 알고리즘
혜덕hyeduck
2024. 4. 3. 21:02
알고리즘 문제) BOJ 1726. 로봇
문제 요약
- 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나
- 로봇 제어 명령어
- Go k: k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다.
- Turn dir: dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다.
- 0은 궤도가 깔려 있어 로봇이 갈 수 있는 지점이고, 1은 궤도가 없어 로봇이 갈 수 없는 지점
- 로봇의 현재 위치와 바라보는 방향이 주어졌을 때, 로봇을 원하는 위치로 이동시키고, 원하는 방향으로 바라보도록 하는데 최소 몇 번의 명령이 필요한지 구하는 프로그램을 작성
시간 제한
- 2초
입력
- 궤도 설치 상태를 나타내는 직사각형의 세로 길이 M과 가로 길이 N
- M과 N은 둘 다 100이하의 자연수
- M줄에 걸쳐 한 줄에 N개씩 각 지점의 궤도 설치 상태를 나타내는 숫자 0 또는 1이 빈칸을 사이에 두고 주어진다
- 로봇의 출발 지점의 위치 (행과 열의 번호)와 바라보는 방향
- 로봇의 도착 지점의 위치 (행과 열의 번호)와 바라보는 방향
- 방향은 동쪽이 1, 서쪽이 2, 남쪽이 3, 북쪽이 4
- 출발지점에서 도착지점까지는 항상 이동이 가능
출력
- 로봇을 도착 지점에 원하는 방향으로 이동시키는데 필요한 최소 명령 횟수
코드
import java.io.*;
import java.util.*;
// 메모리 초과 이슈
public class Main {
static int M, N;
static int[][] arr;
static int sr, sc, sd, er,ec, ed;
static boolean[][][] visited;
// 동북서남 (동1->0 / 서2->2 / 북4->1 / 남3->3)
static int[] delR = {0, -1, 0, 1};
static int[] delC = {1, 0, -1, 0};
static class Node implements Comparable<Node> {
int row;
int col;
int dir;
int cmd;
Node(int row, int col, int dir, int cmd) {
this.row = row;
this.col = col;
this.dir = dir;
this.cmd = cmd;
}
@Override
public int compareTo(Node node) {
return this.cmd - node.cmd;
}
}
static boolean boundaryCheck(int row, int col) {
return 0 <= row && 0 <= col && row < M && col < N;
}
static int bfs(int row, int col, int dir) {
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(row, col, dir, 0));
visited[dir][row][col] = true;
int cr, cc, cd, cm, nr, nc, nd, size;
while (!pq.isEmpty()) {
size = pq.size();
for (int s = 0; s < size; s++) {
cr = pq.peek().row;
cc = pq.peek().col;
cd = pq.peek().dir;
cm = pq.poll().cmd;
if (cr == er && cc == ec && cd == ed) return cm;
// 명령 1 : Go K (1~3) 해당 방향으로 K만큼 이동
// 명령 2 : Turn dir (left or right) 각각 왼쪽 또는 오른쪽으로 90도 회전
/* 나올 수 있는 경우
현재 방향으로 +1,+2,+3 이동
왼쪽 90도 회전 후 +1,+2,+3 이동 (dir+1)%4
동0 -> 북1 / 북1 -> 서2 / 서2 -> 남3 / 남3 -> 동0
오른쪽 90도 회전 후 +1,+2,+3 이동 (dir+3)%4
동0 -> 남3 / 남3 -> 서2 / 서2 -> 북1 / 북1 -> 동0
*/
// 회전 안하고 K이동 -> 여기서 주의할 것 -> k만큼 이동하는 과정에서 1이 있으면 안 됨
for (int i = 1; i <= 3 ; i++) {
nr = cr + delR[cd] * i;
nc = cc + delC[cd] * i;
if (!boundaryCheck(nr,nc) || visited[cd][nr][nc]) continue;
if (arr[nr][nc] == 1) break;
pq.offer(new Node(nr, nc, cd, cm + 1));
visited[cd][nr][nc] = true;
}
// 왼쪽 회전
nd = (cd + 1) % 4;
if (!visited[nd][cr][cc]) {
pq.offer(new Node(cr, cc, nd, cm + 1));
visited[nd][cr][cc] = true;
}
// 오른쪽 회전
nd = (cd + 3) % 4;
if (!visited[nd][cr][cc]) {
pq.offer(new Node(cr, cc, nd, cm + 1));
visited[nd][cr][cc] = true;
}
}
}
return 0;
}
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());
arr = new int[M][N];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
st = new StringTokenizer(br.readLine());
sr = Integer.parseInt(st.nextToken()) - 1;
sc = Integer.parseInt(st.nextToken()) - 1;
sd = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
er = Integer.parseInt(st.nextToken()) - 1;
ec = Integer.parseInt(st.nextToken()) - 1;
ed = Integer.parseInt(st.nextToken());
// 방향 수정한 방식으로 바꿔주기
if (sd == 1) sd = 0;
else if (sd == 4) sd = 1;
if (ed == 1) ed = 0;
else if (ed == 4) ed = 1;
visited = new boolean[4][M][N];
bw.write(String.valueOf(bfs(sr, sc, sd)));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 2412. 암벽 등반
문제 요약
- 암벽에 n(1 ≤ n ≤ 50,000)개의 홈이 파져 있다
- 홈의 좌표는 (x, y)와 같이 표현
- |a - x| ≤ 2이고 |b - y| ≤ 2이면 (x, y)에서 (a, b)로 이동할 수 있다
- 홈들을 이용하여 이동하면서 y = T(1 ≤ T ≤ 200,000)일 때까지, 즉 암벽의 정상까지 오르려고 한다
- 현재 당신이 있는 위치는 (0, 0)
- 이 위치에서 시작하여 이동 회수를 최소로 하면서 정상에 오르려고 한다
- x좌표는 아무 것이나 되어도 상관이 없다
시간 제한
- 2초
입력
- 첫째 줄에 n, T
- 다음 n개의 줄에는 각 점의 x, y좌표
- 두 좌표는 모두 0이상이며, x좌표는 1,000,000이하, y좌표는 T이하
출력
- 첫째 줄에 최소 이동 회수를 출력
- 정상에 오를 수 없으면 -1을 출력
접근법
5 3
1 2
6 3
4 1
3 2
0 2
- (0,0) 에서 이동 가능한 좌표
- x좌표 : -2~2
- y좌표 : -2~2
- (0,2)
- x : -2~2
- y : 0~4
- (1,2)
- x : -1~3
- y : 0 ~ 4
- (3,2)
- x : 1~5
- y : 0~4
- (4,1)
- x : 2~6
- y : -1~3
- 위 과정에서 바로 (0,0)에서 (1,2)로 이동했다면 총 4번만 이동하면 된다!
- 현재 위치에서 배열에 담겨진 암벽들의 좌표들 중 이동 가능하고, 방문하지 않은 애들만 큐에 담으면서 bfs 돌리기!
- 이떄 y==T인 구간에서 멈추기!
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, T;
static int[][] stones;
static ArrayList<Integer>[] list;
static boolean[] visited;
// N이 50000개까지 가능
// for문을 전부 탐색하지말고 이동 가능한 부분만 탐색하게 바꾸기
static int bfs(int y, int i) {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{y, i});
visited[i] = true;
int cy, ci, ny, size, dist = 0;
while (!q.isEmpty()) {
size = q.size();
for (int s = 0; s < size; s++) {
cy = q.peek()[0];
ci = q.poll()[1];
if (cy == T) return dist;
for (Integer ni : list[ci]) {
if (visited[ni]) continue;
ny = stones[ni][1];
q.offer(new int[]{ny, ni});
visited[ni] = true;
}
}
dist++;
}
return -1;
}
// 이동 가능한 범위 중 가장 작은 인덱스 값 출력
static int lowerBound(int s, int e, int key) {
int m;
int answer = e;
while (s <= e) {
m = (s + e) / 2;
if (stones[m][0] < stones[key][0] - 2) {
// 현재 중간값의 x가 이동할 수 있는 x값 보다 작은 값일 때
s = m + 1;
} else if (stones[key][0] + 2 < stones[m][0]) {
// 현재 중간값의 x가 이동할 수 있는 x값 보다 큰 값일 떄
e = m - 1;
} else {
// x간 이동이 가능 함
answer = m;
// 하지만 이동 가능한 좌표들 중 가장 작은 값을 구할 것이므로
e = m - 1;
}
}
return answer;
}
// 이동 가능한 범위중 가장 큰 인덱스값 출력
static int upperBound(int s, int e, int key) {
int m;
int answer = e;
while (s <= e) {
m = (s + e) / 2;
if (stones[m][0] < stones[key][0] - 2) {
// 현재 중간값의 x가 이동할 수 있는 x값 보다 작은 값일 때
s = m + 1;
} else if (stones[key][0] + 2 < stones[m][0]) {
// 현재 중간값의 x가 이동할 수 있는 x값 보다 큰 값일 떄
e = m - 1;
} else {
// x간 이동이 가능 함
answer = m;
// 하지만 이동 가능한 좌표들 중 가장 작은 값을 구할 것이므로
s = m + 1;
}
}
return 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));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
T = Integer.parseInt(st.nextToken());
list = new ArrayList[N + 1];
for (int i = 0; i < N + 1; i++) {
list[i] = new ArrayList<>();
}
stones = new int[N + 1][2];
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
stones[i][0] = Integer.parseInt(st.nextToken());
stones[i][1] = Integer.parseInt(st.nextToken());
}
// x좌표 기준 정렬
Arrays.sort(stones, (o1, o2) -> {
if(o1[0] == o2[0]) return o1[1] - o2[1];
else return o1[0] - o2[0];});
// 위 두 범위를 모두 충족하는 좌표만 리스트에 담기
int lowerX, upperX;
for (int i = 0; i <= N; i++) {
lowerX = lowerBound(0, N, i);
upperX = upperBound(0, N, i);
for (int j = lowerX; j <= upperX ; j++) {
if (Math.abs(stones[i][1] - stones[j][1]) <= 2) {
list[i].add(j);
}
}
}
visited = new boolean[N + 10];
bw.write(String.valueOf(bfs(0, 0)));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 13910. 개업
문제 요약
- 주문 받은 짜장면의 수와 가지고 있는 웍의 크기가 주어질 때, 최소 몇 번의 요리로 모든 주문을 처리할 수 있는지 출력하는 프로그램을 작성
- 조건 → ex) 짜장면 4그릇을 주문 받았는데 5그릇 이상을 요리하지 않으며, 4그릇을 요리할 수 있는 웍에 3그릇 이하의 요리를 하지 않는다.
시간 제한
- 1초
입력
- 첫 번째 줄에는 해빈이가 주문 받은 짜장면의 수N(1≤N≤10,000)과 가지고 있는 웍의 개수 M(1≤M≤100)
- 두 번째 줄에는 웍의 크기 Si(1≤Si≤N)이 M개가 주어지며 같은 크기의 웍을 여러 개 가지고 있을 수 있다
출력
- 모든 주문을 처리하기 위해 해야 하는 최소 요리 횟수를 출력
- 만약 모든 주문을 처리 할 수 없는 경우 -1을 출력
접근법
8 1 4 5
⇒ 무조건 큰 걸로 나누면 안됨
⇒ bfs
⇒ 동시에 여러 웍으로 요리 가능하니까 주의 ⇒ 시간초과 뜰까 무작정 투포인터 갈기지 말기
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static int[] arr;
static boolean[] visited;
static int bfs(int start) {
Queue<Integer> q = new LinkedList<>();
q.offer(start);
int cnt = 0, cur, nxt, size, s, e;
while (!q.isEmpty()) {
size = q.size();
for (int i = 0; i < size; i++) {
cur = q.poll();
if (cur == N) return cnt;
// 웍을 동시에 사용할 수 있음 -> 주의
for (int j = 0; j < M; j++) {
for (int k = 0; k < M; k++) {
nxt = j == k ? cur + arr[j] : cur + arr[j] + arr[k];
if (10000 < nxt || visited[nxt]) continue;
if (N < 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());
arr = new int[M];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
visited = new boolean[10010];
Arrays.sort(arr);
bw.write(String.valueOf(bfs(0)));
bw.flush();
bw.close();
br.close();
}
}