[백준Java]2589 보물섬

문제

---

2589번: 보물섬 (acmicpc.net)

2589번: 보물섬

 

 

기본적인 bfs문제였다. 한가지 주의해야할점은 한곳에서 bfs를 돌려주는 것이 아니라, 각 L마다 모두 bfs를 돌려줘야 한다는 것이었다.

풀이방법

---

• x좌표, y좌표, count를 가지고 있는 Node를 만든다.
• 배열을 입력받고 L이 나올때마다 bfs 함수를 돌린다.
• 상, 하, 좌, 우를 확인하면서, nx>=0 && nx<N && ny>=0 && ny<M && map[nx][ny]=='L' && visit[nx][ny]==false를 충족하는 Node를 큐에 방문처리를 하면서 넣어준다.
• 이 과정에서 최댓값을 구한 후 return하고 이중에서 최댓값을 구해 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;

class nodelist{
	int x;
	int y;
	int count;
	
	public nodelist(int x, int y, int count) {
		super();
		this.x = x;
		this.y = y;
		this.count = count;
	}
}

public class Main{
	static int del[][] = {{-1,0},{1,0},{0,-1},{0,1}}; //위 아래 왼 오 
	static char map[][];
	static int N,M;
	static boolean visit[][];
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		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 char[N+1][M+1];
		for(int i=0; i<N; i++) {
			String s = br.readLine();
			for(int j=0; j<M; j++) {
				map[i][j]=s.charAt(j);
			}
		}
		
		int result=Integer.MIN_VALUE;
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j]=='L') {
					visit=new boolean[N][M];
					result=Math.max(go(i,j), result);
				}
			}
		}
		System.out.println(result);

	}
	static int go(int x, int y) {
		
		Queue<nodelist> queue= new LinkedList<>();
        visit[x][y]=true;
		queue.add(new nodelist(x,y,0)); //큐에다가 첫번째 노드를 생성해서 넣음
		int c=0;
		int max=Integer.MIN_VALUE;
		while(!queue.isEmpty()) {
				nodelist get = queue.poll();//큐에 있는 원소 빼기
				int gx=get.x; //x좌표
				int gy=get.y; //y좌표
				
				c = get.count; //count
						
				for(int k=0; k<4; k++) {
					int nx=gx+del[k][0]; //주변에 갈 x좌표
					int ny=gy+del[k][1];

					if(nx>=0 && nx<N && ny>=0 && ny<M && map[nx][ny]=='L' && visit[nx][ny]==false) {
						visit[nx][ny]=true;
						queue.add(new nodelist(nx,ny,c+1));
						max=Math.max(c+1, max);
						
						}
					}
				
				}

		return max;
		}
		
		
	}