[백준] 알고리즘 분류(브루트 포스,JAVA)2589번, 보물섬

문제 링크

2589번: 보물섬

---

주의사항

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

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

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. L은 땅, W는 바다를 표현합니다.

2. 보물은 육지를 나타내는 두 곳에 최단거리로 이동할 때 가장 먼 거리에 뭍혀있습니다.

3. 상하좌우 1칸씩 이동이 가능하며 이동시 1시간이 걸립니다.

4. 두 곳 사이를 최단 거리로 이동하는 시간을 결과로 출력합니다.

5. 같은 곳을 2번 이상 지나가지 못하며 바다로도 이동하지 못합니다.

 

알고리즘 진행 순서.

 

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

 

2. 각 육지에서 BFS탐색으로 다른 육지까지의 최단 거리를 구합니다.

 

3. 최단 거리 중 가장 긴 거리를 결과로 출력합니다.

 

 

예제입력 2.

 

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

 

L : 5

W : 7

 

W	L	L	W	W	W	L
L	L	L	W	L	L	L
L	W	L	W	L	W	W
L	W	L	W	L	L	L
W	L	L	W	L	W	W

 

2. 각 육지에서 BFS탐색으로 다른 육지까지의 최단 거리를 구합니다.

 

(0, 1)에 BFS 탐색!

W	L	L	W	W	W	L
L	L	L	W	L	L	L
L	W	L	W	L	W	W
L	W	L	W	L	L	L
W	L	L	W	L	W	W

가장 큰 최단 거리 : 6(4, 1)

 

(3, 0)에 BFS 탐색!

W	L	L	W	W	W	L
L	L	L	W	L	L	L
L	W	L	W	L	W	W
L	W	L	W	L	L	L
W	L	L	W	L	W	W

가장 큰 최단 거리 : 8(4, 1)

 

(0, 6)에 BFS 탐색!

W	L	L	W	W	W	L
L	L	L	W	L	L	L
L	W	L	W	L	W	W
L	W	L	W	L	L	L
W	L	L	W	L	W	W

가장 큰 최단 거리 : 7(3, 6)

 

3. 최단 거리 중 가장 긴 거리를 결과로 출력합니다.

 

8시간(3, 0)을 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 통해서 L과 W를 띄어쓰기 기준으로 나누었습니다.
• bfs함수를 이용하여 각 땅에서 다른 땅에 최단 거리들을 구하였습니다.
• 최단 거리 중 가장 큰 값을 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs함수는 BFS탐색으로 각 땅에서 다른 땅에 최단 거리를 구합니다.
• inSpace함수는 BFS탐색시 지도에 벗어나는지 확인합니다.

 

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


public class Main {
    //지도 위치 정보 관련 클래스
    static class position{
        int x, y, count;
        public position(int x, int y, int count){
            this.x = x;
            this.y = y;
            this.count = count;	//이동한 횟수
        }
    }
    static int L,W, max = Integer.MIN_VALUE;
    static char[][] map;	//지도 정보 배열
    static boolean[][] visited;	//방문 확인 배열
    static int[] dx = {0, 0, -1, 1};	//상하좌우 X변경값
    static int[] dy = {-1, 1, 0, 0};	//상하좌우 Y변경값
    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 = new StringTokenizer(br.readLine(), " ");
        L = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());
        map = new char[L][W];
        //지도 정보 저장
        for(int i=0;i<L;i++){
            String str = br.readLine();
            for(int j=0;j<W;j++)
                map[i][j] = str.charAt(j);
        }
        //각 땅에서 다른 땅에 최단 거리 구하는 BFS 탐색
        for(int i=0;i<L;i++){
            for(int j=0;j<W;j++){
                if(map[i][j] == 'L')
                    bfs(i, j);
            }
        }
        bw.write(max + "");	//최단 거리들에서 가장 큰 값 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //최단 거리를 구하는 BFS함수
    static void bfs(int y, int x){
        Queue<position> q = new LinkedList<>();
        visited = new boolean[L][W];
        visited[y][x] = true;
        int count = 0;
        q.add(new position(x, y, 0));
        while(!q.isEmpty()){
            position cur = q.poll();
            boolean check = false;
            //상하좌우 인접한 공간 탐색
            for(int i=0;i<4;i++){
                int tempX = dx[i] + cur.x;
                int tempY = dy[i] + cur.y;
                //인접한 공간이 방문하지 않았던 땅인 경우.
                if(inSpace(tempX,tempY) && !visited[tempY][tempX] && map[tempY][tempX]== 'L'){
                    visited[tempY][tempX] = true;
                    q.add(new position(tempX,tempY, cur.count+1));
                    check = true;
                }
            }
            if(!check)
                count = Math.max(cur.count,  count);
        }
        max = Math.max(max, count);
    }
    //BFS탐색으로 이동하려는 공간이 존재하는지 확인하는 함수
    static boolean inSpace(int x, int y){
        if(x>=0 && y>=0 && x<W && y<L)
            return true;
        return false;
    }
}