> For the complete documentation index, see [llms.txt](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/bfs-getting-minimum-value/treasure-island.md).

# Treasure Island

* **알고리즘 생각**\
  1\. 일단 (0,0)에서 시작하여 (r,c)까지 순회하는 BFS를 구현하여 d배열 중 가장 큰값을 리턴하도록 만든다.\
  2\. 1에서 발전시키기\
  \- main : 1에서 시작점을 (0,0)으로 고정하는 것이 아니라 (0,0) \~(r,c) 사이 모든 좌표가 시작점이 되도록 이중 for문으로 구현한다.\
  \- bfs 함수 : 거리값을 저장하는 배열 d도 bfs 내에서 초기화한다.\
  새로운 시작점에 대해 d배열의 최댓값을 새로이 생성하여 리턴한다.
* **코드 최적화 - 실패, 실패원인 분석**\
  2차원 배열 값을 입력받으면서 값이 'L'이면 bfs를 진행하여 정답을 도출하고자 했다.\
  디버깅 결과 d배열값이 제대로 기록되지 않음을 확인할 수 있었다. \
  그 이유는 (i,j)값을 입력받고 값이 'L' 을 만족하여 bfs를 순회할지라도, (i+1,j+1) \~(r-1,c-1) 입력값은 미지의 값이기 때문에 bfs 내에서 상하좌우 탐색 및 값 세팅하는 데에 조건을 만족하지 않기 때문에 d배열 값이 제대로 기록되지 않기 때문이다!!!!

따라서 이 방법으로 코드 최적화를 할 순 없다. 2차원 배열값을 다 입력받은 후에 bfs를 실행하고, 정답을 도출해야 한다!

![(0,1)에서 시작하는 bfs 실행 후 d배열 값](/files/-MbzEjXaY_OiwBRk14sa)

```java
import java.util.*;
class TI{
	int x, y;
	TI(int x,int y){
		this.x = x;this.y = y;
	}
}
public class TreasureIsland {
	public static int r;
	public static int c;
	public static char[][] a;
	public static int[][] d;
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
	public static int bfs(int x,int y) {//(0,1)
		for(int i=0;i<r;i++) {
			for(int j=0;j<c;j++) {
				d[i][j] = -1;
			}
		}
		int ans = -1;
		Queue<TI> q = new LinkedList<TI>();
		q.add(new TI(x,y));//(0,1)추가.
		d[x][y] = 0;//시작좌표 d[x][y] = d[0][1] = 0.
		while(!q.isEmpty()) {
			TI cur = q.remove();
			for(int i=0;i<4;i++) {
				int nx = cur.x+dx[i];
				int ny = cur.y+dy[i];
				if(nx<0 || nx>r-1 || ny<0 || ny>c-1) continue;
				if(a[nx][ny] == 'L' && d[nx][ny]==-1) {
					q.add(new TI(nx,ny));
					d[nx][ny] = d[cur.x][cur.y]+1;
				}
			}
		}
		for(int i=0;i<r;i++) {//디버깅용 d출력.
			for(int j=0;j<c;j++) {
				System.out.printf("%3d",d[i][j]);
			}
			System.out.println();
		}
		for(int i=0;i<r;i++) {
			for(int j=0;j<c;j++) {
				if(ans == -1||ans<d[i][j]) {ans = d[i][j];}
			}
		}
		System.out.println("ans  : "+ans);
		return ans;
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		r = sc.nextInt();
		c = sc.nextInt();
		a = new char[r][c];
		d = new int[r][c];
		sc.nextLine();
		int res = -1;
		for(int i=0;i<r;i++) {
			String s = sc.nextLine();
			for(int j=0;j<c;j++) {
				a[i][j] = s.charAt(j);
				if(a[i][j]=='L') {//(0,1)
					if(res == -1 || res<bfs(i,j)) {
						res = bfs(i,j);
					}
				}
			}
		}
		//System.out.println();
		System.out.println(res);
	}

}

```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://heunnajo.gitbook.io/algorithms-problem-solving-skills/bfs-getting-minimum-value/treasure-island.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.