1. 문제 설명

여러 칸으로 나뉘어져 있는 직사각형의 지도 (가로와 세로의 크기는 각각 50 이하)

각 칸은 육지(L)나 바다(W)로 표시되어 있음

이 지도에서 상하좌우로 이웃한 육지로만 이동 가능하며, 한 칸 이동하는데 한 시간 소요됨

보물은 서로 간에 최단 거리로 이동하는 데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있음

육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가면 안 됨

보물 지도가 주어질 때, 보물이 뭍혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하여라

// [input]
5 7
WLLWWWL
LLLWLLL
LWLWLWW
LWLWLLL
WLLWLWW

// [output]
8

2. 스크래치

문제 유형 파악

1. 알고리즘 유형: BFS
   보물의 위치: ****보물은 두 지점 사이에 최단 거리로 이동 && 가장 긴 시간이 걸리는 육지 두 곳
   한 정점에서 다른 모든 정점까지의 최단 거리를 구할 때 → BFS
   두 L정점의 최단 거리 중 가장 큰 값 찾기

⇒ bfs로 육지의 두 정점사이를 최단 거리로 이동하는 데 그 값들 중 가장 큰 값을 찾는 문제

1. 각 클러스터별 최대길이 찾기 (maxDist 변수)
   전체 맵 탐색 → L 발견 → 모든 L에 대해 BFS 수행 → maxDist 갱신

3. 풀이: BFS

문제 쪼개기

[전역 변수]

int N, M // 맵의 가로 & 세로 크기 
char [][] map // 2차원 배열 지도
int maxDist=0 // 두 정점 사이의 최댓값 저장
int[] dr // 4방향 탐색: 행의 값 변화
int[] dc // 4방향 탐색: 열의 값 변화

• 가로 크기 = 행 / 세로 크기 = 열

[main]

main()
	1. [input]
		- N, M
		- map[N][M] 
	
	2. [logic]
		for( i=0 ~ N)
			for (j=0 ~ M) 
				map[i][j] == 'L'
					findMaxDist(i,j)

	3. [output]
	sysout(maxDist)

• 2중 for문으로 탐색해서 해당 좌표값이 L이라면 다른 정점L까지의 최대 거리 갱신
• for문을 모두 순회하고 최대 길이 출력

[f: findMaxDist]

static void findMaxDist(int i, int j)
	1. visited[N][M] 초기화: false
		 visited[i][j] = t
	
	2. 큐 생성
		 q <- (i,j,0) // 현재 행, 열, 거리 누적값 넣기
		 
	3. while(!q.isEmpty())
		currR, currC, currD = q.poll()
		
		maxDist 갱신 = maxDist(currD, maxDist)
		
		4방향 탐색
			newR, newC
			1) isValid 체크 -> 아니면 continue
			2) visited 체크 ->  true면 continue
			3) map[newR][newC] != 'L'이면 continue
			4) visited[newR][newC] = true
			5) 큐에 (newR, newC, currD+1) 추가 
	

4. 코드

public class Main {
	static int N,M;
	static char[][] map;
	static int maxDist = 0;
	static int[] dr= {-1,1,0,0};
	static int[] dc= {0,0,-1,1};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		// [input]
		String[] tmp = br.readLine().split(" ");
		
		N = Integer.parseInt(tmp[0]); // 세로 크기 = 행의 개수
		M = Integer.parseInt(tmp[1]); // 열
		
		map = new char[N][M];
		
		for(int i=0; i<N; i++) {
				String temp = br.readLine();
			for(int j=0; j<M; j++) {
				map[i][j]=temp.charAt(j);
			}
		}
		
		//System.out.println(Arrays.deepToString(map));
		
		
		 // [logic]
		// 모든 육지 쌍 중 가장 긴 최단거리
		for(int i=0; i<N; i++) {
			for(int j=0; j<M;j++) {
				if (map[i][j]=='L') { // !! 모든 L에 대해
					findMaxDist(i,j);
				}
			}
		}
		
		// [output]
		System.out.println(maxDist);
		
	
	}// main

	// 하나의 클러스터당 돌릴 bfs
	private static void findMaxDist(int cr, int cc) {
		boolean[][] visited = new boolean[N][M];
		visited[cr][cc]=true;
		
		Deque<int[]> q = new ArrayDeque<>();
		q.add(new int[] {cr, cc,0}); // 현재 행, 열, 거리 누적값
		
		while(!q.isEmpty()) {
			int[] currRCD = q.poll();
			int currR = currRCD[0];
			int currC = currRCD[1];
			int currD = currRCD[2];
			
			maxDist = Math.max(currD, maxDist);
			
			for(int d=0; d<4; d++) {
				int newR = currR + dr[d];
				int newC = currC + dc[d];
				
				if(newR<0|| newR >=N || newC<0|| newC>=M) continue;
				
				if(!visited[newR][newC]&& map[newR][newC]=='L') {
					visited[newR][newC] = true;
					q.add(new int[] {newR,newC,currD+1}); //!! 한 레벨씩 거리 증가시키기 
				}
			}
			
	
		}
		
	}// f: findMaxDist

}

시간복잡도

for (int i=0; i<N; i++) {
    for (int j=0; j<M; j++) {
        if (map[i][j] == 'L') {
            findMaxDist(i, j);   // BFS 실행
        }
    }
}

모든 칸을 돌면서 값이 L일 경우마다 BFS 수행

• BFS 수행 횟수
  최악의 경우: 모든 칸이 L → L * M 번
• BFS 한 번의 시간 복잡도
  큐에 노드를 한 번씩 넣고 최대 4방향을 탐색
  visited 배열로 중복이 방지 → 한 BFS 내에서 각 칸은 최대 1번 방문
• O((N × M) × (N × M)) = O((N × M)²)

5. De-fault

fault 1. visited 배열의 위치 & 탐색 조건

❌ boolean[][] visited 배열을 main 함수에서 선언해서
방문하지 않은 L만 bfs 하는 방식 → 섬이 여러 개로 나눠지 경우 한 번만 탐색하도록 함

...
static boolean[][] visited;

public static void main(String[] args) {
	...
	// visited 배열 초기화
	visited = [N][M];
	...
	
		// X 방문하지 않은 L에 대해서만 X
	for(int i=0; i<N; i++){
		for(int j=0; j<M; ++) {
			if(map[i][j]=='L' && !visited[i][j]){
				findMaxDist(i,j);
			}
		}
	}

✅ 모든 좌표의 L을 시작점으로 BFS를 돌려야 하는 이유
각 L이 속한 클러스터 안에서 그 지점이 클러스터의 끝단이 아닐 수도 있기 때문에
모든 L을 시작점으로 BFS를 한 번씩 수행하면, 모든 가능한 경로를 다 탐색하게 되어 전역적으로 최대 거리를 보장할 수 있음 (완전 탐색 방식)

• BFS를 한 번 돌릴 때 시작점 기준으로만 최단 거리를 계산함
  어떤 육지 L에서 BFS를 시작하느냐에 따라 얻는 최장 거리가 달라짐
• e.g. 일자형 맵에서

  L L L L L

  (0,0)에서 BFS → 최장 거리 = 4 (0,2)에서 BFS → 최장 거리 = 2 (0,4)에서 BFS → 최장 거리 = 4 ⇒ 중간에서 시작하면 실제 최대 지름을 얻지 못함
  
• BFS 함수 내부 visted 배열 선언
  모든 L에 대해 BFS를 돌리기 때문에, 각 BFS가 완전히 새 출발점이어야 함
  ⇒ visited는 각 BFS 시작점마다 초기화 되어야 함

이 코드에서 잘못된 부분이나 개선할 점이 있다면 언제든지 댓글로 알려주세요.
알고리즘을 작성하면서 더 좋은 코드를 만들 수 있도록 도와주시면 정말 감사하겠습니다! 🙂