[백준, Java] 25417번, 고속의 숫자 탐색(BFS)

문제 링크

25417번: 고속의 숫자 탐색

---

주의사항

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

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

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. 5 x 5 크기의 보드가 존재하며, -1, 0, 1, 7 중 1개의 숫자가 적혀있습니다.

2. 보드에서는 상하좌우 1칸씩 이동하거나, 멈추는 조건까지 뛰어갈 수 있습니다.

3. 보드 경계면에 도착하거나 -1, 7을 만났을 때 멈추게 됩니다.

4. 시작 위치가 주어질 때 보드 1이 적힌 위치까지 도달하는 최소 이동 횟수를 결과로 출력합니다.

5. 1이 적힌 공간을 방문하지 못하면 -1을 결과로 출력합니다.

 

 

알고리즘 진행 순서.

 

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

 

2. BFS을 통해서 1이 적힌 위치까지 도달하는 최소 이동 경로를 탐색합니다.

 

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

 

 

1이 적힌 공간까지 최소 이동 경로 찾기(BFS)

 

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

 

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

 

또한, 상하좌우 방향으로 뛰어갈 수 있으며 보드에 경계/-1/7이 될 때까지 이동합니다.

 

0(→)	0	0(도착)	-1	0
0(→)	0	7(도착)	0	0
0(→)	0	0	0	0(도착)

 

위와 같이 뛰어가서 멈추는 조건에 맞는 위치에 도달하게 됩니다.

 

 

시작 위치를 기준으로 BFS을 진행하여 1이 적힌 구역까지 이동하는 경로를 탐색합니다.

 

 

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

 

예제입력 1.

 

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

 

[보드]

 

0	0	1	0	0
0	7	-1	0	0
0	0	0	0	0
0	0	-1	0	0
0	0(시작 위치)	0	-1	0

 

2. BFS을 통해서 1이 적힌 위치까지 도달하는 최소 이동 경로를 탐색합니다

 

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

 

 

0	0	1	0	0
0	7	-1	0	0
0	0	0	0	0
0	0	-1	0	0
0	0	0	-1	0

 

 

 

0	0	1	0	0
0	7	-1	0	0
0	0	0	0	0
0	0	-1	0	0
0	0	0	-1	0

 

0	0	1	0	0
0	7	-1	0	0
0	0	0	0	0
0	0	-1	0	0
0	0	0	-1	0

 

 

 

탐색 종료.

 

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

 

 

 

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

 

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

 

 

3 결과로 출력합니다.

 

 

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

• search함수는 BFS을 통해서 1이 적힌 공간까지 방문하는 최소 이동 횟수를 탐색합니다.
• inSpace함수는 이동하려는 공간이 보드에 존재하는지 확인합니다.

결과코드

import java.io.*;
import java.util.*;
public class Main {
    //보드 이동 정보 관련 클래스
    static class Pos{
        int r, c, distance;
        Pos(int r, int c, int distance){
            this.r = r;
            this.c = c;
            this.distance = distance;
        }
    }
    //보드 정보 저장 배열
    static int[][] map;
    //상하좌우 r, c의 변경값
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    //보드 크기
    static final int SIZE = 5;
    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[SIZE][SIZE];
        //보드 정보 저장
        for(int i=0;i<SIZE;i++){
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<SIZE;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을 통해서 1번 구역에 도착하는 최소 이동 횟수를 구하기.
        int answer = search(r, c);
        //최소 이동 횟수 BufferedWriter 저장
        bw.write(String.valueOf(answer));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    
    //BFS을 통해서 1번 구역에 도착하는 최소 이동 횟수 구하는 함수
    static int search(int r, int c){
        Queue<Pos> q = new ArrayDeque<>();
        //시작 위치 Queue 저장
        q.offer(new Pos(r, c, 0));
        int[][] distance = new int[SIZE][SIZE];
        //최소 이동 횟수 배열 초기화
        for(int i=0;i<SIZE;i++){
            Arrays.fill(distance[i], Integer.MAX_VALUE);
        }
        distance[r][c] = 0;
        //BFS 탐색 시작
        while(!q.isEmpty()){
            Pos cur = q.poll();
            //1이 적힌 공간에 도착했을 때
            if(map[cur.r][cur.c] == 1){
                return cur.distance;
            }
            int nxtDistance = cur.distance + 1;
            //상하좌우 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 && distance[nr][nc] > nxtDistance){
                    distance[nr][nc] = nxtDistance;
                    q.offer(new Pos(nr, nc, nxtDistance));
                }
            }
            //상하좌우 뛰어갈 때
            for(int i=0;i<4;i++){
                int nr = cur.r;
                int nc = cur.c;
                //멈추는 조건까지 뛰어가기
                while(true){
                    int tempR = nr + dr[i];
                    int tempC = nc + dc[i];
                    //보드에 경계를 만나거나 -1을 만났을 때
                    if(!inSpace(tempR, tempC) || map[tempR][tempC] == -1){
                        break;
                    }
                    nr = tempR;
                    nc = tempC;
                    //7이 적힌 공간을 만났을 때
                    if(map[nr][nc] == 7){
                        break;
                    }
                }
                if(distance[nr][nc] > nxtDistance){
                    distance[nr][nc] = nxtDistance;
                    q.offer(new Pos(nr, nc, nxtDistance));
                }
            }
        }
        return -1;
    }
    //이동하려는 칸이 보드 내에 존재하는지 확인하는 함수
    static boolean inSpace(int r, int c){
        return r >= 0 && r < SIZE && c >= 0 && c < SIZE;
    }
}