[백준, Java] 25513번, 빠른 오름차순 숫자 탐색(BFS)

문제 링크

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

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. 5 x 5 크기의 보드가 존재하며, 각 격자에는 -1, 0, 1, 2, 3, 4, 5, 6이 적혀있습니다.

2. -1은 갈 수 없는 공간이고, 0 ~ 6까지 순서대로 방문해야 합니다.

3. 0 → 1으로 순차적으로 증가하지 않고, 0 → 5처럼 이동할 수 있습니다.

4. (r, c)시작 지점을 기준 0 ~ 6까지 방문하는 최소 이동 횟수를 결과로 출력합니다.

5. 0 ~ 6까지 방문하지 못하면 -1을 결과로 출력합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. BFS을 통해서 0 ~ 6까지 방문하는 최소 이동 횟수를 탐색합니다.

 

3. 탐색을 통해 얻은 최소 이동 횟수를 결과로 출력합니다.

 

 

0 ~ 6 순으로 방문하도록 이동하기(BFS)

 

보드에서는 상하좌우로 이동할 수 있습니다.

 

	(-1, 0)
(0, -1)	위치	(0, 1)
	(1, 0)

 

 

BFS을 진행하기 앞서, 보드를 이동할 때 방문했던 곳을 재방문할 수 있습니다.

 

해당 과정에 조건을 걸지 않으면 멈추지 않고 계속 탐색할 것입니다.

 

그래서, 문제에서는 최소 이동 횟수를 구해야하기 때문에 중복 방문했을 때 이동한 거리보다 크면 해당 방문은 최소 이동 횟수가 아니기 때문에 해당 탐색은 종료되도록 해야 합니다.

 

int[5][5][6] 크기의 3차원 배열로 최소 이동 횟수를 관리할 것입니다.

 

int[i][j][k] : k의 수까지 지났을 때 (i, j) 보드 공간에 방문한 최소 이동 횟수

 

만약, int[2][2][3] = 4일 때 동일한 조건으로 (2, 2)을 방문했을 때 이동 횟수가 5번이면 해당 탐색은 더 이상 탐색하지 않아도 된다는 것입니다.

 

시작 위치(r, c)를 기준으로 BFS을 진행합니다.

 

시작 위치는 항상 0이기 때문에 0을 탐색을 진행하였다고 가정하고 BFS 탐색을 진행합니다.

 

다른 구역에 방문할 때 int[i][j][k]을 통해서 최소 이동 횟수가 될 때 탐색을 지속합니다.

 

 

※예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

[보드]

 

0	0(시작 위치)	1	0	0
0	0	2	0	0
0	0	3	0	0
0	0	4	0	0
0	0	5	6	-1

 

 

2. BFS을 통해서 0 ~ 6까지 방문하는 최소 이동 횟수를 탐색합니다.

 

시작 위치(0, 1)기준 BFS 진행

 

 

0	0	1	0	0
0	0	2	0	0
0	0	3	0	0
0	0	4	0	0
0	0	5	6	-1

 

 

 

0	0	1	0	0
0	0	2	0	0
0	0	3	0	0
0	0	4	0	0
0	0	5	6	-1

 

 

0	0	1	0	0
0	0	2	0	0
0	0	3	0	0
0	0	4	0	0
0	0	5	6	-1

 

0	0	1	0	0
0	0	2	0	0
0	0	3	0	0
0	0	4	0	0
0	0	5	6	-1

 

0	0	1	0	0
0	0	2	0	0
0	0	3	0	0
0	0	4	0	0
0	0	5	6	-1

 

0	0	1	0	0
0	0	2	0	0
0	0	3	0	0
0	0	4	0	0
0	0	5	6	-1

 

탐색 종료.

 

(0, 1) → (0, 2) → (1, 2) → (2, 2) → (3, 2) → (4, 2) → (4, 3) 

 

 

 

3. 탐색을 통해 얻은 최소 이동 횟수를 결과로 출력합니다.

 

(0, 1) → (0, 2) → (1, 2) → (2, 2) → (3, 2) → (4, 2) → (4, 3)  :  6번 이동

 

 

6 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 이용해서 보드의 정보를 띄어쓰기 기준 나누었습니다.
• 시작 위치를 기준으로 search을 통해 구역을 탐색합니다.
• 모든 탐색이 끝났을 때 최소 이동 횟수를 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search함수는 BFS을 통해서 0 ~ 6까지 방문하는 최소 이동 횟수를 탐색합니다.
• search함수는 공간을 방문할 때 dist[][][]배열의 최소 이동 횟수를 기준으로 계속 탐색할 지 결정합니다.
• inSpace함수는 이동하려는 공간이 보드에 존재하는지 확인합니다.

결과코드

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

public class Main {
    //보드 이동 정보 클래스
    static class Pos{
        int r, c, nxt, dist;
        Pos(int r, int c, int nxt, int dist){
            this.r = r;
            this.c = c;
            this.nxt = nxt;
            this.dist = dist;
        }
    }
    //상하좌우 r, c 변경 값
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    //보드 정보 저장 배열
    static int[][] map;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        map = new int[5][5];
        //보드 정보 저장
        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 r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        //BFS을 통해 최소 이동 횟수 찾기
        int answer = search(r, c);
        //최소 이동 횟수 BufferedWriter 저장
        bw.write(String.valueOf(answer));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //BFS을 통해서 0 ~ 6 순으로 방문하는 최소 이동 횟수 구하는 함수
    static int search(int r, int c){
        Queue<Pos> q = new ArrayDeque<>();
        int[][][] dist = new int[5][5][7];
        //최소 이동 횟수 배열 나올 수 없는 최대값으로 설정
        for(int i=0;i<5;i++){
            for(int j=0;j<5;j++){
                Arrays.fill(dist[i][j], Integer.MAX_VALUE);
            }
        }
        //시작 위치 저장
        q.offer(new Pos(r, c, 0, 0));
        //BFS 진행
        while(!q.isEmpty()){
            Pos cur = q.poll();
            //순서대로 6번째 공간 도착했을 때
            if(cur.nxt == 6){
                return cur.dist;
            }
            int nxtDis = cur.dist + 1;
            //상하좌우 이동
            for(int i=0;i<4;i++){
                int nr = cur.r + dr[i];
                int nc = cur.c + dc[i];
                //방문할 수 있는 공간일 때
                if(inSpace(nr, nc) && map[nr][nc] != -1 ) {
                    int nxtVisit = cur.nxt;
                    //다음 번호의 공간일 때
                    if(map[nr][nc] == nxtVisit+1){
                        nxtVisit++;
                    }
                    //최소 이동 횟수가 아닐 때
                    if(dist[nr][nc][nxtVisit] <= nxtDis) {
                        continue;
                    }
                    //다음 공간 Queue 저장
                    dist[nr][nc][nxtVisit] = nxtDis;
                    q.offer(new Pos(nr, nc, nxtVisit, nxtDis));
                }
            }

        }
        // 0 ~ 6순으로 방문하지 못할 때
        return -1;

    }
    //보드 공간에 존재하는지 확인하는 함수
    static boolean inSpace(int r, int c){
        return r>=0 && r<5 && c>=0 && c<5;
    }
}