[ 백준 25416 ] 빠른 숫자 탐색

1. 문제

25416번: 빠른 숫자 탐색

 

2. 풀이

전형적인 미로 탐색 문제이다. BFS의 개념을 이해하고 있다면 Standard와 같은 문제이므로 큰 어려움 없이 풀이가 가능하다.

네 방위(동, 서, 남, 북)로 움직일 수 있는 학생이 움직일 수 없는 조건에 대해서만 적절하게 체크해주면 풀이가 가능하다. 까다로운 조건 없이 좌표계에서 이동만 하는 것이며, `1`이 적힌 어딘가에 있는 지점으로 도달해야하므로 BFS가 가장 적합한 수단이라고 볼 수 있다. 

 

학생이 움직일 수 없는 조건

• 이동하고자 하는 지점에 -1이 적혀 있는 경우
• 이미 방문한 곳을 다시 방문하고자 하는 경우

두 번째 조건의 경우 BFS로 풀이하기 위한 추가 조건이며, 이차원 정수 배열을 사용하여 각 지점에 도달할 시에 거리를 업데이트 해준다. 이 때, 업데이트된 지점으로 방문하고자 할 경우 이는 이미 최소 경로로 탐색이 된 지점이므로 탐색에서 배제하기 위함이다.

 

그 외의 특이점이라면 1이 적힌 지점에 도달할 수 없는 경우 -1을 반환해야 하므로 이것에 대한 처리만 적절히 잘 해주면 된다.

 

3. 소스코드

public class Main {

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

    static int[][] map = new int[5][5];
    static int[][] visit = new int[5][5];

    static int bfs(int r, int c) {
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(r, c));
        visit[r][c] = 0;

        while (!q.isEmpty()) {
            Point now = q.poll();
            for (int dir = 0; dir < 4; dir++) {
                int ny = now.y + dy[dir];
                int nx = now.x + dx[dir];

                if (!canVisit(ny, nx)) continue;

                if (map[ny][nx] == 1) return visit[now.y][now.x] + 1;

                q.add(new Point(ny, nx));
                visit[ny][nx] = visit[now.y][now.x] + 1;
            }
        }

        return -1;
    }

    static boolean canVisit(int y, int x) {
        return 0 <= y && 0 <= x && y < 5 && x < 5 && visit[y][x] == -1 && map[y][x] != -1;
    }

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

        for (int i = 0; i < 5; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 5; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                visit[i][j] = -1;
            }
        }

        st = new StringTokenizer(br.readLine());

        bw.write(bfs(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())) + "");
        bw.flush();
        bw.close();
        br.close();
    }

    static class Point {
        int y, x;

        public Point(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }
}

Problem Solved: 25416번 빠른 숫자 탐색 · kwanik-kor/BOJ@6f85432

 

---

BFS 개념은 아래 게시글을 참고♥️

그래프와 BFS(Graph & Breadth First Search)