[백준] 미로 탐색 2178번 - Java
나의 풀이
class Node {
int x;
int y;
Node (int x, int y) {
this.x = x;
this.y = y;
}
}
public class MazeExploration {
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static int[][] graph = new int[100][100];
static boolean[][] visited = new boolean[100][100];
static int N;
static int M;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] items = br.readLine().split(" ");
N = Integer.parseInt(items[0]);
M = Integer.parseInt(items[1]);
for(int i = 0; i < N; i++) {
String[] values = br.readLine().split("");
for(int j = 0; j < M; j++) {
graph[i][j] = Integer.parseInt(values[j]);
}
}
System.out.println(bfs(0, 0));
}
static private int bfs(int x, int y) {
Queue<Node> queue = new LinkedList<>();
queue.offer(new Node(x, y));
visited[x][y] = true;
while(!queue.isEmpty()) {
Node node = queue.poll();
for(int i = 0; i < 4; i++) {
int nx = node.x + dx[i];
int ny = node.y + dy[i];
if(nx < 0 || ny < 0 || nx >= N || ny >= M) {
continue;
}
if(graph[nx][ny] == 0) {
continue;
}
if(!visited[nx][ny] && graph[nx][ny] == 1) {
graph[nx][ny] = graph[node.x][node.y] + 1;
visited[nx][ny] = true;
queue.offer(new Node(nx, ny));
}
}
}
return graph[N - 1][M - 1];
}
}
- bfs를 사용하여 접근하였다.
- bfs에서 사용하기 위해서 상, 하, 좌, 우 좌표, 2차 배열, visited 등 클래스 변수를 선언해준다.
- 그리고 좀 더 편하게 하기 위해서 x, y 변수를 가진 Node 클래스를 작성하였다.
- 이제 좌표 0, 0 부터 배열의 끝 까지 탐색을 시작한다.
- bfs는 큐를 이용하기 때문에 큐를 만들어 준다. 그리고 큐에 입력받은 좌표를 갖는 노드 클래스를 초기화하여 큐에 담아준다. 그리고 해당 좌표는 방문처리를 한다.
- 이제 큐가 비어있지 않은 동안 큐에서 해당 노드를 꺼내고, 4방향을 체크한다.
- 만약 현재 위치로부터 상, 하, 좌, 우 중에서 배열의 범위를 벗어난다면 continue를 통해 해당 방향은 스킵한다.
- 그리고 만약 배열에서 해당 좌표의 값이 0이라면 스킵한다.
- 마지막으로 만약 방문 처리가 되지 않았고, 해당 좌표의 값이 1이라면 해당 좌표에 그 전에 있던 좌표의 배열값을 더해주고, 방문 처리를 한다. 그리고 해당 좌표로 노드 클래스를 다시 초기화하여서 큐에 넣어준다. 이렇게 되면 방문 처리가 되지 않고, 좌표의 값이 1인 좌표를 만날 때 마다 노드를 추가하여 반복이 끊이지 않고 계속 탐색을 할 수 있다.
- 만약 더 이상 좌표의 값이 1이고 방문 처리가 되지 않은 위치를 탐색할 수 없으면 반복이 종료되고 좌표의 제일 마지막 값을 리턴해준다.
Author And Source
이 문제에 관하여([백준] 미로 탐색 2178번 - Java), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@goshk95/백준-미로-탐색-2178번-Java저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)