백준 2178_미로 탐색_JAVA

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

 

import java.util.*;
import java.io.*;

public class Main {
    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-1};
    static int N,M; // 행과 열을 받을 int
    static int[][] grid; // 그래프
    static boolean[][] visited; // 방문결과


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        grid = new int[N][M];
        visited = new boolean[N][M];

        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            String line = st.nextToken();
            for(int j=0; j<M; j++) {
                grid[i][j] = Integer.parseInt(line.substring(j, j+1)); // String 잘라 int형으로 변환 후 넣기
            }
        }

        BFS(0,0,1); // x좌표, y좌표, 몇번째 노드인지 count
    }

    private static void BFS(int x, int y, int c) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {x,y,c});
        // 지금 방문 중이니 방문 결과 true로 변경
        visited[x][y] = true;

        while(!queue.isEmpty()) {
            // 가장 먼저 들어온 데이터 추출
            int[] cur = queue.poll();

            // 만약 x,y 좌표가 우리가 구하는 좌표면 while문 break 후 count 출력
            if(N-1 == cur[0] && M-1 == cur[1]) {
                System.out.print(cur[2]);
                break;
            }
            for(int i=0; i<4; i++) { // 그래프 상하좌우 탐색
                int next_x = cur[0] + dx[i];
                int next_y = cur[1] + dy[i];
                int next_c = cur[2] + 1;
                
                if(next_x >= 0 && next_y >= 0 && next_x < N && next_y < M && grid[next_x][next_y] == 1 && !visited[next_x][next_y]) {
                    visited[next_x][next_y] = true;
                    queue.add(new int[] {next_x, next_y, next_c});
                }
            }
        }
    }
}

 

 

회고

- BFS 기초문제였다.

- java로 bfs를 구현하는 것에 익숙해져서 좋다.

 

 

 

다시 풀었을때

import java.io.*;
import java.util.*;

public class Main {
    static int N, M;
    static int[][] grid;
    static boolean[][] visited;

    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 행
        M = Integer.parseInt(st.nextToken()); // 열
        grid = new int[N][M];
        visited = new boolean[N][M];

        for(int i = 0; i<N; i++) {
            String line = br.readLine();
            for(int j = 0; j<M; j++) {
                grid[i][j] = Integer.parseInt(line.substring(j,j+1)); // 하나씩 잘라 int로 변환후 grid에 대입
            }
        }

        System.out.print(BFS(0,0,1)); // 칸의 수니까 본인도 1칸
    }

    public static int BFS(int x, int y, int c) {
        Queue<int[]> queue = new LinkedList<>();
        visited[x][y] = true;
        queue.add(new int[] {x,y,c});

        while(!queue.isEmpty()) {
            int[] cur = queue.poll();
            int cur_x = cur[0];
            int cur_y = cur[1];
            int cur_c = cur[2];

            if(cur_x == N-1 && cur_y == M-1) {
                return cur_c;
            }

            for(int i = 0; i<4; i++) {
                int nx = cur_x + dx[i];
                int ny = cur_y + dy[i];
                int nc = cur_c + 1;

                if(nx>=0 && ny >=0 && nx<N && ny<M && !visited[nx][ny] && grid[nx][ny] == 1) {
                    visited[nx][ny] = true;
                    queue.add(new int[] {nx, ny, nc});
                }
            }
        }
        return 0;
    }
}