[백준] 미로 탐색 2178번 - Java

GoshK·2022년 2월 18일
0

[백준] Java

목록 보기
45/49
post-thumbnail

[백준] 미로 탐색 2178번

나의 풀이

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이고 방문 처리가 되지 않은 위치를 탐색할 수 없으면 반복이 종료되고 좌표의 제일 마지막 값을 리턴해준다.

0개의 댓글