[백준 2589] 보물섬

문제 이해는 했는데 방향을 잘못잡아서 꽤 헤맸던 문제...

1. DFS로 가장 큰 육지 구하고

2. BFS로 가장 거리 멀리 있는 두점 구하고!

3. 최단거리 구하고! 

ㅋ...ㅋ....ㅋ.ㅋㅋㅋㅋㅋㅋㅋ

---

📌최단거리 = BFS

BFS로 구하면 최단거리가 나온다! 

 

주어진 MAP에서 각 L이 있는 지점을 하나씩 시작점이라고 생각하고 BFS를 다 연산해본다.

그중 가장 큰 값이 나오는 것이 보물의 위치(서로 가장 먼값)면서 최단거리인값....!

 

문제에서 주어진 map의 bfs돌아가는 순서

사진을 보면 가장 큰 값이 멀리 있으면서 최단거리이다

---

 

 

데이터 테스트 해볼거 추가!

https://www.acmicpc.net/board/view/40753

참고 했습니다.

 

ex1) 답 : 2

2 2
LL
LL

 

ex2) 답 : 6

7 7
LWWWWWW
WLLLWWW
WLLLWWW
WLLLWWW
WWWWLLW
WLLLLLW
WLLWWWL

 

---

package BJ;

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

class Point { //point객체 만들기
	int x;
	int y;
	
	Point(int x, int y){
		this.x = x;
		this.y = y;
	}
}

public class bj2589 {
	public static char[][]  arr; // 입력받은 행렬
	public static boolean[][]  visited; //방문했는지 체크
	public static int[][] ans; // 거리를 저장해주는 행렬
	public static int[] dx = {-1,1,0,0};// 한 포인트에서 갈수 있는 4방향 움직이기위한 도구
	public static int[] dy = {0,0,-1,1};// 한 포인트에서 갈수 있는 4방향 움직이기위한 도구
	public static int max = 0;
	
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt();
		int w = sc.nextInt();
		arr = new char[h][w];
		
		for(int i=0; i<h; i++) {
			arr[i] = sc.next().toCharArray();
		}
		

		for(int i=0; i<h; i++) {
			for(int j=0;j<w;j++) {
				if(arr[i][j] == 'L') {
					visited = new boolean[h][w]; //L인 애들 하나씩 시작점으로 다 돌려본다
					ans = new int[h][w];
					bfs(i,j);
				}
			}
		}
		
		System.out.println(max);
		
	}
	
	public static void bfs(int i, int j) {
		
		Queue<Point> que = new LinkedList<Point>();
		
		visited[i][j] = true;
		que.add(new Point(i,j));
		
		int temp = 0;
		
		while(!que.isEmpty()) {
			int xx = que.peek().x;
			int yy = que.peek().y;
			que.poll();
			
			for(int k=0;k<4;k++){
				int xxx = dx[k] + xx;
				int yyy = dy[k] + yy;
				
				if(xxx>=0&& yyy>=0&& xxx<arr.length && yyy<arr[0].length) {
					if(arr[xxx][yyy] == 'L' && !visited[xxx][yyy]) {
						que.add(new Point(xxx,yyy));
						visited[xxx][yyy] = true;
						ans[xxx][yyy]= ans[xx][yy]+1; //거리를 하나씩 늘려가줌
						
						if(temp < ans[xxx][yyy]) {
							temp = ans[xxx][yyy]; //시작점에서의 최대값 구하기
						}
					}
				}
			}
			
		}
		
		if(max<temp) { // 각 시작점 중에서의 최대값 구하기 
			max = temp;
		}
		
	}
	
	
}

---

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

2589번: 보물섬