[백준] 2178: 미로 탐색 - Java (그래프 이론)
Algorithm/BackJun 2024. 1. 11.
목 차
- 문제
- 접근 방식
- 이 문제를 구현하며 알게된 것
- 풀이
문제
접근 방식
이번에는 BFS 알고리즘으로 해당 문제를 해결하려고 한다. BFS는 가장 먼저 도착하는 것을 반환하면 되기 때문에 생각보다 간단하다.
자바에는 컬렉션에 Queue 자료구조가 있어 그 것을 활용하면 된다.
근데 LinkedList 의 Queue 는 객체로 되어있어 메모리를 상당히 잡아먹는다.
그래서 나는 배열 형태의 Queue 자료구조를 만들기로 했다. 근데 javascript 와는 달리 Java 의 배열은 정적 배열이기에 Javascript 의 .push 같은 배열 메서드가 제공되지 않는다.
그래서 원형 큐(Circular Queue)를 알게되었고, 대안으로 선택하게 되었다. 원형 큐는 다음 소제목 '이 문제를 구현하며 알게된 것' 에서 언급하겠다.
이 문제는 weight 값만 추가하여 [N][M]에 도착했을 때의 weight 값을 출력하며 된다.
이 문제를 구현하며 알게된 것
원형 큐(Circular Queue)
front 와 end 포인터가 있을 때, end를 ++ 할 때 queue.length 와 같다면 end 를 0 으로 만든다.
front 역시 ++ 했을 때 queue.length 와 같다면 front 역시 0 으로 만든다.
풀이
package src.graph;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class maze {
public static void main(String[] args) throws Exception {
// 입력
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
final int N = Integer.parseInt(st.nextToken());
final int M = Integer.parseInt(st.nextToken());
int[][] graph = new int[N + 2][M + 2];
// 입력 배열화
for(int i = 1; i <= N; i++){
String mazeTokens = br.readLine();
for(int j = 0; j < M; j++){
graph[i][j+1] = mazeTokens.charAt(j) - '0';
}
}
int[] first = {1, 1, 1};
// Main
// Queue 자료구조 - for BFS
Queue queue = new Queue(100);
queue.enqueue(first);
while(!queue.isEmpty()){
int[] data = queue.dequeue();
int x = data[1];
int y = data[0];
int w = data[2];
if(x == M && y == N) {
System.out.println(w);
break;
}
graph[y][x] = 0;
// 상
if(graph[y - 1][x] != 0){
int[] point = {y - 1,x , w + 1};
graph[y - 1][x] = 0;
queue.enqueue(point);
}
// 하
if(graph[y + 1][x] != 0){
int[] point = {y + 1,x , w + 1};
graph[y + 1][x] = 0;
queue.enqueue(point);
}
// 우
if(graph[y][x + 1] != 0){
int[] point = {y, x + 1 , w + 1};
graph[y][x + 1] = 0;
queue.enqueue(point);
}
// 좌
if(graph[y][x - 1] != 0){
int[] point = {y,x - 1, w + 1};
graph[y][x - 1] = 0;
queue.enqueue(point);
}
}
}
public static class Queue {
private int[][] queue;
private int front;
private int end;
private int capacity;
public Queue(int size){
queue = new int[size][3];
front = 0;
end = 0;
capacity = size;
}
public void enqueue(int[] el){
// 추가사항: 용량이 꽉 차면 에러 발생
queue[end] = el;
end++;
if(end == capacity) end = 0;
}
public int[] dequeue(){
// 추가사항: 비어있다면 에러 발생
int[] data = queue[front];
front++;
if(front == capacity) front = 0;
return data;
}
public boolean isEmpty(){
return front == end;
}
public boolean isFull(){
if(((end + 1 == capacity) && front == 0) || (end + 1 == front)) {
return true;
} else {
return false;
}
}
}
}
'Algorithm > BackJun' 카테고리의 다른 글
[백준] 11727: 2 * n 타일링2 - Java (DP) (0) | 2024.01.14 |
---|---|
[백준] 2606: 바이러스 - Java (그래프 이론) (0) | 2024.01.11 |
[백준] 1932: 정수 삼각형 - Java (DP) (0) | 2024.01.11 |
[백준] 11726: 2 * n 타일링 - Java (DP) (0) | 2024.01.07 |
[백준] 2775: 부녀회장이 될테야 - Java (DP) (0) | 2024.01.07 |