문제

보물섬

풀이

저는 BFS가 직관적이라고 생각해서 좋아합니다 (잘하는 것과는 별개로...)
한번에 풀지는 못했지만 3트를 하여 이렇게 풀었습니다

1. BFS

	private static int bfs(int x, int y) {
        int result = 0;
        Queue<int[]> q = new LinkedList<>();
        // 시작점
        q.add(new int[]{x, y});
        visited[x][y] = 1;
        while (!q.isEmpty()) {
            int[] current = q.poll();
            for (int i = 0; i < 4; i++) {
                int nx = current[0] + dx[i];
                int ny = current[1] + dy[i];
                if (nx >= 0 && ny >= 0 && nx < l && ny < w 
                	&& visited[nx][ny] == 0 && map[nx][ny] == 'L') {
                	// 이전 시점에서 한시간 걸린다
                    visited[nx][ny] = visited[current[0]][current[1]] + 1;
                    q.add(new int[]{nx, ny});
                    // 시작점에서 현재까지 가장 멀리 간 거리
                    result = Math.max(result, visited[nx][ny] - 1);
                }
            }
        }
        return result;
    }

1,2트에서 간과한 점은 visited[x][y] 시작점 방문처리를 하지 않았다는 거였습니다. 그리고 시작점의 위치에서 1부터 방문처리를 해주기위해 1을 입력했으므로 result를 갱신할때 이 점을 빼주어야 합니다.

2. 매 땅의 시점마다 깊이를 갱신해주어야 한다

		int answer = 0;
        for (int i = 0; i < l; i++) {
            for (int j = 0; j < w; j++) {
                if (map[i][j] == 'L') {
                    visited = new int[l][w];
                    answer = Math.max(bfs(i, j), answer);
                }
            }
        }

전체 코드

전체 코드