문제 풀이(6)

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

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

class Node{
	int x;
	int y;
	int depth;

	Node(int x , int y ,int depth)
	{
		this.x = x;
		this.y = y;
		this.depth = depth;
	}

}

class Main {

	static char[][] matrix;

	static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};

	static boolean[][] visited;

	static int N , M;
	
	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());

		matrix = new char[N][M];

		visited = new boolean[N][M];

		for (int i = 0; i < N; i++) {

			String str = br.readLine();

			for (int j = 0; j < M; j++) {
				matrix[i][j] = str.charAt(j);
			}

			
		}

	
        int result = 0;

		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (matrix[i][j] == 'L') {
					
                    visited = new boolean[N][M];
                    
					int value = bfs(i,j);

                    result = Math.max(result , value);
					
				}
			}
		}


		System.out.println(result);

	
	}

	public static int bfs(int a , int b)
	{
		Queue<Node>Q = new LinkedList<>();

		Q.offer(new Node(a, b, 0));
        
        visited[a][b] = true;

		int max = 0;

		while (!Q.isEmpty()) {
			
			Node now = Q.poll();

			for (int k = 0; k < dir.length; k++) {
				
				int nx = now.x + dir[k][0];

				int ny = now.y + dir[k][1];

				if (nx < 0 || ny < 0 || nx >= N || ny >= M) {
					continue;
				}

				if (visited[nx][ny]) {
					continue;
				}

				if (matrix[nx][ny] == 'W') {
					continue;
				}

				visited[nx][ny] = true;

				Q.offer(new Node(nx, ny, now.depth + 1));
                
                max = Math.max(max,now.depth + 1);
			}

		}


		//System.out.println(max);

		return max;
	}
}

입력을 받아서 matrix 배열에 지도 정보를 저장하고, visited 배열을 초기화한다.모든 칸을 순회하며 'L'을 찾는다. 'L'을 찾으면 해당 좌표에서 bfs 함수를 호출하여 최대 이동 시간을 계산한다.각 칸에서 bfs 함수는 너비 우선 탐색으로 최단 거리를 계산하고, 해당 칸에서의 최대 이동 시간을 반환한다.모든 'L'을 순회하며 최대 이동 시간의 최댓값을 갱신하여 출력한다.