백준 2589 <보물섬>

일단 최단거리를 찾는 문제이기 때문에 BFS를 사용하는 것은 확실한 문제

 

그러나 가장 멀리 떨어진 지점을 어떻게 선택할까?라는 고민을 했던 문제.

 

일방적으로는 가장 끝지점을 고르면 되지 않을까? 하지만 예외상황이 있을 수 있음!

 

그렇기 때문에 생각한 방법은 완전 탐색으로 모든 지점에서 돌려보는 것!!!

 

시간 초과는 50*50이 맵 크기 이므로 50*50*50*50=6250000 625만 이므로 절대 터지지 않는다!!

 

그러므로 답은 bfs를 모든 지점에서 돌려 보는 것!

 

문제 풀이

 

1. L인 모든 좌표에서 BFS를 해서 가장 긴 길이를 리턴한다.

 

끝?!

 

 

좌표 x, y와 길이를 나타낼 d를 담을 클래스를 선언한다.

 

BFS에서 핵심인 부분 뒤에 남은 큐가 없다는 것은 가장 긴 지점이므로 그 값을 저장한다.

 

while 문을 벗어나게 되면 max값과 result값을 비교해서 result에 넣어주면 문제 해결 끝!

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static class who{
		int x;
		int y;
		int d;
		public who(int x, int y, int d) {
			super();
			this.x = x;
			this.y = y;
			this.d = d;
		}
	}
	static int n,m;
	static String map[];
	static int result=0;
	static int dir[][]= {{-1,0},{0,1},{1,0},{0,-1}};
	private static void bfs(int x, int y,int n,int m) {
		// TODO Auto-generated method stub
		int max=0;
		boolean visit[][]=new boolean[n][m];
		visit[x][y]=true;
		Queue<who> q=new LinkedList<who>();
		q.add(new who(x,y,0));
		while(!q.isEmpty()) {
			who next=q.remove();
			if(q.isEmpty()) {
				max=next.d;
			}
			for(int i=0;i<4;i++) {
				int x1=next.x+dir[i][0];
				int y1=next.y+dir[i][1];
				if(x1<0||x1>=n||y1<0||y1>=m) {
					continue;
				}
				if(map[x1].charAt(y1)=='W'||visit[x1][y1]) {
					continue;
				}
				visit[x1][y1]=true;
				q.add(new who(x1,y1,next.d+1));
			}
		}
		if(result<max) {
			result=max;
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		n=Integer.parseInt(st.nextToken());
		m=Integer.parseInt(st.nextToken());
		map=new String[n];
		for(int i=0;i<n;i++) {
			map[i]=br.readLine();
		}
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				if(map[i].charAt(j)=='L') {
					bfs(i,j,n,m);
				}
			}
		}
		System.out.println(result);
	}
} // end of class