1. queue를 두개를 만들어서 고슴도치가 움직이는 queue, 물이 차는 queue를 만들어서 bfs를 돈다. 이게 최선일 것 같은느낌..?
코드
정답 코드 : 기본적인 BFS 문제인 것 같다. 중간에 코드를 잘 못 적어서 1시간 삽질했다..
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int N, M, minValue, destinationX, destinationY;
static Queue<int[]> HedgehogQueue, waterQueue;
static char[][] array;
static boolean[][] check;
static int[] x = { -1, 1, 0, 0 };
static int[] y = { 0, 0, -1, 1 };
public static void main(String[] args) throws Exception {
SetData();
bfs();
if (minValue == Integer.MAX_VALUE)
System.out.println("KAKTUS");
else
System.out.println(minValue);
}
private static void SetData() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
array = new char[N][M];
check = new boolean[N][M];
HedgehogQueue = new LinkedList<>();
waterQueue = new LinkedList<>();
minValue = Integer.MAX_VALUE;
String s;
for (int i = 0; i < N; i++) {
s = br.readLine();
for (int j = 0; j < M; j++) {
array[i][j] = s.charAt(j);
if (array[i][j] == 'D') {
destinationX = i;
destinationY = j;
} else if (array[i][j] == 'S') {
HedgehogQueue.offer(new int[] { i, j, 0 });
check[i][j] = true;
} else if (array[i][j] == '*') {
waterQueue.offer(new int[] { i, j });
}
}
}
}
private static void bfs() {
while (!HedgehogQueue.isEmpty()) {
int size = waterQueue.size();
for (int i = 0; i < size; i++) {
int location[] = waterQueue.poll();
for (int direction = 0; direction < 4; direction++) {
int r = location[0] + x[direction]; // 물 방향
int c = location[1] + y[direction];
if (r < 0 || r >= N || c < 0 || c >= M)
continue;
if (array[r][c] != '.')
continue;
array[r][c] = '*';
waterQueue.offer(new int[] { r, c });
}
}
size = HedgehogQueue.size();
for (int i = 0; i < size; i++) {
int location[] = HedgehogQueue.poll();
int count = location[2];
if (location[0] == destinationX && location[1] == destinationY) {
minValue = Math.min(minValue, count); // 마지막 위치에 도달했을 때 지나온 칸 수를 return
}
for (int direction = 0; direction < 4; direction++) {
int r = location[0] + x[direction]; // 고슴도치 방향
int c = location[1] + y[direction];
if (r < 0 || r >= N || c < 0 || c >= M)
continue;
if (check[r][c] || array[r][c] == '*' || array[r][c] == 'X')
continue;
check[r][c] = true;
HedgehogQueue.offer(new int[] { r, c, count + 1 });
}
}
}
}
}
1. dfs로 푸는 방법 - 정확하게 풀 수 있다. 벽을 부수고 지나왔으면 그 다음 벽은 못 부수게 하면되고 안부수고 지나왔으면 다음 벽을 만났을 때 부술 수 있게 돌리면 된다. 최종으로 도달했을 때 가장 짧은 길이를 출력 ==>> 시간 초과
위의 사진은 어떤 분이 정리 해 둔 것인데 보면서 깨달으면 좋을 것 같아서 가져왔다.
가중치가 없는 최단 경로는 무조건 BFS입니다.왜 DFS가 안 될까요? 그 이유는 당연하게도, 특정 칸에 처음 도달했을 때까지의 경로의 길이가 다른 경로를 통해 도달한 길이보다 짧다는 보장이 전혀 없기 때문입니다. 아직까지 이 사실을 모르고 계셨다면, 이 문제는 아직 풀기에 너무 어렵습니다. 더 기본적인 BFS 문제을 먼저 풀어보세요.
모든 칸을 전부 0으로 하나씩 바꾸어보고 BFS를 돌리는 것을 반복해서는 통과될 수 없습니다. 대부분의 알고리즘 문제가 그렇듯이, 풀이를 짜기 전에 반드시 해야 하는 것 중 하나는 시간 복잡도를 생각하는 것입니다. 시간 복잡도 계산, 전혀 어렵지 않습니다. 벽이 최대 O(NM)개 있는 맵에서, 벽을 하나 부술 때마다 O(NM)개의 칸을 탐색해야 하죠? 그러니 O((NM)^2)입니다. 이 수는 우리가 대충 1초에 돌 수 있다고 보는 단위인 1억을 10000배나 뛰어넘는 1조입니다. 절대 통과될 수 없겠죠?
칸마다 방문 체크 하나씩만 하는 방법으로는 풀 수 없습니다. 어떤 칸에 도달했을 때 나는 "아직 벽을 부술 수 있는 상태"일 수도 있고, "더 이상 벽을 부술 수 없는 상태"일 수도 있습니다.큐에 그 상태를 넣은 것만으로 되는 것이 아닙니다. 당장 이 지점까지 어떻게든 최단으로 오는 길만 구했다고 해서, 그 이후의 여정도 최적으로 만들 수 있는 건 아닙니다. 구체적인 예시가 필요한가요?
현재 칸까지 벽을 안 부수고 최단으로 올 수 있었다고 가정해봅시다. 현재 지점에서 목표 지점까지 가는 데에, 벽을 한 개 부수고 가는 것이 안 부수고 가는 것보다 최적이 나온다고 해봅시다. 그렇다면 지금 내가 벽을 더 부술 수 있는 상태라는 사실을 알고 있어야만 되겠죠?
벽을 안 부수고도 현재 칸까지 도달이 가능하지만, 벽을 부수고 오는 것이 더 짧다고 가정해봅시다. 현재 지점에서 목표 지점까지 가려면 무조건 벽을 한 개 부숴야만 된다고 해봅시다. 비록 현재 칸까지는 벽을 부수고 오는 것이 최적이었지만, 이 상태로는 끝에 아예 도달을 못 하죠? 현재 칸까지는 더 멀더라도 벽을 안 부수고 와야, 끝에 도달이 가능하죠.
(스포일러)그래서 이 문제에서는 BFS에 대해 새로운 테크닉을 요구합니다. 단순히 좌표만을 큐에 넣어 탐색하는 방식을 넘어, "현재 상태" 자체를 큐에 넣어서 문제를 풀어야 합니다. 즉, 어떤 좌표에 있는가 뿐만 아니라, "여기까지 오면서 벽을 부순 적이 있는가" 여부를 함께 큐에 저장해서 탐색하고,각각을 별개로 방문 체크해줘야 하는 문제입니다. visited[x][y]가 아니라, visited[x][y][벽을 부순 적이 있는가?] 가 되어야 합니다.
이 문제에서는 같은 칸에 방문하는 경우 벽을 안 부순 것이 더 유리하기 때문에 벽을 부쉈는지 여부를 방문 배열에 기록하여 부순 횟수가 더 적을 때만 방문하는 방법도 됩니다. 그러나 이는 문제의 특성 때문에 이 문제에서만 통하는 그리디이므로 다른 문제에도 함부로 사용해서는 안 됩니다.
2. bfs로 푸는 방법 - 조건을 잘 설정하면 dfs보다 메모리는 더 쓰겠지만 속도는 빠를 것 같다. (시간과 메모리 제한 보고 알고리즘을 생각하는 정도의 수준까지 오면 좋을 것 같다. ==>> 공부를 열심히 해야할 듯.)
코드
정답 코드 : bfs로 풀었다. 여기서 핵심은 중복제거를 check[N][M][2]로 벽을 지나오면서 왔는지 아닌지 중복체크를 해주는 방법을 사용해야지만 정확히 풀 수 있는 문제이다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int N, M, minValue;
static int[][] array;
static boolean[][][] check;
static int[] x = { -1, 1, 0, 0 };
static int[] y = { 0, 0, -1, 1 };
public static void main(String[] args) throws Exception {
SetData();
bfs();
if(minValue == Integer.MAX_VALUE)
System.out.println(-1);
else
System.out.println(minValue);
}
private static void SetData() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
array = new int[N][M];
check = new boolean[N][M][2];
minValue = Integer.MAX_VALUE;
String s;
for (int i = 0; i < N; i++) {
s = br.readLine();
for (int j = 0; j < M; j++) {
array[i][j] = s.charAt(j) - '0';
}
}
}
private static void bfs() {
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[] { 0, 0, 1, 0 });
while (!queue.isEmpty()) {
int location[] = queue.poll();
int count = location[2];
int breakWall = location[3];
if (location[0] == N - 1 && location[1] == M - 1) {
minValue = Math.min(minValue, count); // 마지막 위치에 도달했을 때 지나온 칸 수를 return
}
for (int direction = 0; direction < 4; direction++) {
int r = location[0] + x[direction];
int c = location[1] + y[direction];
if (r < 0 || r >= N || c < 0 || c >= M)
continue;
if (array[r][c] == 1 && breakWall == 1) // 지나온 벽이 있고 다음 칸도 벽이면 진행 X
continue;
if (breakWall == 1) {
if (!check[r][c][breakWall] && array[r][c] == 0) {
check[r][c][breakWall] = true;
queue.offer(new int[] { r, c, count + 1, breakWall});
}
} else { // 벽을 안부순 상태
if (!check[r][c][breakWall] && array[r][c] == 1) {
check[r][c][breakWall] = true;
queue.offer(new int[] { r, c, count + 1, breakWall + 1 });
} else if (!check[r][c][breakWall] && array[r][c] == 0) {
check[r][c][breakWall] = true;
queue.offer(new int[] { r, c, count + 1, breakWall });
}
}
}
}
}
}
1. 문제를 일고 처음에 이해가 되지 않았는데, 예제를 보고선 도킹을 할 때 현재 번호보다 낮은 번호에만 도킹을 할 수 있다는 사실을 알게되었다.
코드
정답 코드 : gate[index] == index 일때만 도킹을 해준다. 도킹을 했을댄 index의 값을 -1해줘서 해당 인덱스에는 다신 도킹할 수 없게 하였다. gate[index] != index 경우에는 해당 게이트보다 낮은 게이트를 재귀로 모두 다 돌아본 다음 도킹 가능한 게이트가 있으면 도킹, index가 0까지 가는 경우 도킹을 종료한다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int G, P;
static int[] gate, airplane;
public static void main(String[] args) throws Exception {
SetData();
System.out.println(FindMaxValue());
}
private static void SetData() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
G = Integer.parseInt(br.readLine());
P = Integer.parseInt(br.readLine());
gate = new int[G + 1];
airplane = new int[P + 1];
for (int i = 1; i <= G; i++)
gate[i] = i;
for (int i = 1; i <= P; i++)
airplane[i] = Integer.parseInt(br.readLine());
}
private static int FindMaxValue() {
int count = 0;
for (int i = 1; i <= P; i++) {
if (docking(airplane[i]) < 0)
break;
count++;
}
return count;
}
private static int docking(int index) {
// basecase (게이트 번호의 값이 0이면 도킹 불가)
if (gate[index] == 0) return -1;
if (gate[index] == index) // 도킹을 아직 시도하지 않은 게이트라면
gate[index]--;
else // 도킹을 한 게이트라면 현재 게이트보다 낮은 게이트를 찾기 위해 재귀를 돔.
gate[index] = docking(gate[index]);
return gate[index];
}
}
1. DFS - 멀티탭의 모든 칸이 꽉 찰때마다 모든 멀티탭의 플러그를 한번씩 빼가며 DFS를 돌림. 정확하지만 시간초과 가능성 높음
2. 멀티탭에 꽂으면서 꽉찼을 때만 뽑을 콘센트를 찾는 작업을 진행함. 콘센트를 빼는 것은 뒤에 가장 적게오는 콘센트를 뽑는다.
코드
정답 코드 : 2번 방법으로 콘센트가 꽉 찼을 때만 뒤에 남아있는 콘센트 번호 중에 가장 적게 나오는 번호를 뽑는다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int N, K;
static int[] array;
static HashSet<Integer> powerSocket; // 멀티탭에 먼저 꽂았는지 꽂지 않았는지는 상관이 없다. HashSet 사용
public static void main(String[] args) throws Exception {
SetData();
System.out.println(FindMinValue());
}
private static void SetData() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
powerSocket = new HashSet<Integer>();
array = new int[K];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < K; i++)
array[i] = Integer.parseInt(st.nextToken());
}
private static int FindMinValue() {
int count = 0;
for(int i = 0; i < K; i++) {
// 콘센트가 꽉차지 않거나 콘센트에 꽂혀있는 번호이면 continue
if(powerSocket.contains(array[i]) || isPossible(array[i]))
continue;
// 콘센트가 꽉차고 콘센트에 꽂혀있는 번호가 아닐 시
int max = -1, pick = -1;
for (int num : powerSocket) {
int temp = 0; // temp를 통해 뒤에 가장 적게 오는 수를 지워줌
for (int j = i + 1; j < K; j++) {
if (num == array[j]) {
break;
}
temp++;
}
if (temp > max) {
pick = num;
max = temp;
}
}
powerSocket.remove(pick);
powerSocket.add(array[i]);
count++;
}
return count;
}
private static boolean isPossible(int item) {
if (powerSocket.size() < N) {
powerSocket.add(item);
return true;
}
return false;
}
}
정답 코드 : 1번 방법은 시간초과가 나올 것 같아서 2번 방법을 시행했다. 2번 방법을 쉽게 푸는 팁이 있다면 array.sort로 배열을 오름차순으로 정렬 후 pritorityqueue 우선순위 큐(큐에 있는 값들이 2개 이상이면 오름차순으로 큐에 들어감)를 사용하여 쉽게 해결할 수 있었다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int N, K;
static int[][] jewelry;
static int[] bag;
static long maxValue;
public static void main(String[] args) throws Exception {
SetData();
FindMaxValue();
System.out.println(maxValue);
}
private static void SetData() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
maxValue = 0;
jewelry = new int[N][2];
bag = new int[K];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
jewelry[i][0] = Integer.parseInt(st.nextToken());
jewelry[i][1] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < K; i++)
bag[i] = Integer.parseInt(br.readLine());
// 2차원 배열 sort
Arrays.sort(jewelry, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
// TODO Auto-generated method stub
return o1[0] - o2[0];
};
});
Arrays.sort(bag);
}
private static void FindMaxValue() {
// 우선 순위 큐로 해야지 오름차순 정렬이 되서 작은 값이 맨 먼저 나오게됌
Queue<Integer> queue = new PriorityQueue<>();
int j = 0;
for (int i = 0; i < K; i++) {
while (j < N && jewelry[j][0] <= bag[i]) { // 앞에서 담은것은 제외해야 하므로 while문과 j를 사용
queue.add(-jewelry[j][1]); // -를 해주는 이유는 -를 해야지 양수 최대값이 음수로 넣었을 때 오름차순에서 맨 앞으로 가져올 수 있게한다.
j++;
}
if (!queue.isEmpty()) { // for문 한번에 한번만 더한다.
maxValue += Math.abs(queue.poll()); // 음수로 바꿔줬던 수에 절대값을 씌워서 양수로 다시 나오게함
}
}
}
}
