[ 백준 25513번 ] 빠른 오름차순 숫자 탐색

1. 문제

25513번: 빠른 오름차순 숫자 탐색

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

 

2. 풀이

전형적인 BFS를 통한 경로탐색 문제이며, 방문해야 하는 노드가 순차적으로 정해져 있는 형태의 문제다. 우선 보드가 5 x 5 로 작은 형태이므로 구현 자체에도 큰 어려움이 없을 것으로 생각된다. 다만, 이미 방문한 노드를 어떻게 다시 방문하지 않을 것인가를 판단하는 것이 중요한데, 대개 이러한 유형의 경우 3차원 배열로 방문배열을 선언하여 현재 탐색중인 idx 에서는 중복된 칸을 방문하지 않도록 처리하면 쉽게 해결할 수 있다.

 

• boolean[][][] visit = new boolean[5][5][7];
  • 5x5 보드에서, (0 ~ 6)까지의 idx를 탐색하는 각각의 과정에서의 방문처리

 

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 boolean[][][] visit = new boolean[5][5][7];

    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());
            }
        }

        st = new StringTokenizer(br.readLine());
        int y = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken());

        bw.write(bfs(y, x) + "");
        bw.close();
        br.close();
    }

    static int bfs(int y, int x) {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(y, x, 0, 0));
        visit[y][x][0] = true;

        while (!q.isEmpty()) {
            Node now = q.poll();
            int idx = now.idx;
            
            // 6번이 적힌 칸에 도달한 경우 종료
            if (idx == 6) {
                return now.cnt;
            }

            for (int dir = 0; dir < 4; dir++) {
                int ny = now.y + dy[dir];
                int nx = now.x + dx[dir];

                if (isOutOfRange(ny, nx) || visit[ny][nx][idx]) continue;

                visit[ny][nx][idx] = true;

                // 다음 번호를 탐색한 경우 idx 증가시켜주기
                int nIdx = idx;
                if (map[ny][nx] == idx + 1) nIdx++;

                q.add(new Node(ny, nx, nIdx, now.cnt + 1));
            }
        }

        return -1;
    }
    
    // 보드를 벗어나거나, -1로 쓰인 칸으로는 진행할 수 없음
    static boolean isOutOfRange(int y, int x) {
        return y < 0 || x < 0 || 5 <= y || 5 <= x || map[y][x] == -1;
    }

    /**
     * y, x : 좌표
     * idx : 현재까지 탐색을 완료한 idx
     * cnt : 현재까지의 경로 길이
     */
    static class Node {
        int y, x, idx, cnt;

        public Node(int y, int x, int idx, int cnt) {
            this.y = y;
            this.x = x;
            this.idx = idx;
            this.cnt = cnt;
        }
    }
}

 

GitHub - kwanik-kor/BOJ: Baekjoon Online Judge - explanation of solved problems and complete code