작성 코드

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

public class treasureisland_2589 {
    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 1};
    static int max_dist;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int row = Integer.parseInt(st.nextToken());
        int col = Integer.parseInt(st.nextToken());

        // L : 1, W : 0
        int[][] arr = new int[row][col];

        for (int i = 0; i < row; i++) {
            String line = br.readLine();
            for (int j = 0; j < col; j++) {
                char c = line.charAt(j);
                if (c == 'L') {
                    arr[i][j] = 1;
                } else {
                    arr[i][j] = 0;
                }
            }
        }

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (arr[i][j] == 1) {
                    int dist = bfs(i, j, arr, row, col);
                    if (max_dist < dist) {
                        max_dist = dist;
                    }
                }
            }
        }

        System.out.println(max_dist);
    }

    public static int bfs(int sy, int sx, int[][] arr, int row, int col) {

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{sy, sx});

        int[][] distance = new int[row][col];
        for (int i = 0; i < row; i++) {
            Arrays.fill(distance[i], -1);
        }

        boolean[][] visited = new boolean[row][col];
        for (int i = 0; i < row; i++) {
            Arrays.fill(visited[i], false);
        }

        visited[sy][sx] = true;
        distance[sy][sx] = 0;
        int max_distance = 0;
        while (!queue.isEmpty()) {
            int[] queue_yx = queue.poll();
            int y = queue_yx[0];
            int x = queue_yx[1];

            for (int d = 0; d < 4; d++) {
                int ny = y + dy[d];
                int nx = x + dx[d];

                if ( 0 <= ny && ny < row && 0 <= nx && nx < col && visited[ny][nx] == false && arr[ny][nx] == 1) {
                    visited[ny][nx] = true;
                    queue.offer(new int[]{ny, nx});
                    distance[ny][nx] = distance[y][x] + 1;
                    if (distance[ny][nx] > max_distance) {
                        max_distance = distance[ny][nx];
                    }
                }
            }
        }

        return max_distance;
    }
}

설명

해당 코드는 보물섬(Treasure Island)의 최장 거리를 구하는 문제를 해결하기 위한 Java 프로그램입니다. 다음은 코드에 사용된 자료구조와 로직에 대한 설명입니다.

• 자료구조

  • int[][] arr: 보물섬 지도를 나타내는 2차원 배열입니다. L은 1로, W는 0으로 표시됩니다.
  • int[] dy와 int[] dx: 상하좌우 이동을 위한 배열입니다. 각 인덱스에 저장된 값은 각각 y와 x 방향으로의 이동 거리를 나타냅니다.
  • Queue<int[]> queue: BFS(Breadth-First Search) 탐색을 위한 큐입니다. 큐에는 좌표를 저장하여 탐색 순서를 관리합니다.
  • int[][] distance: 출발 지점부터의 거리를 나타내는 2차원 배열입니다. 각 좌표까지의 최단 거리가 저장됩니다.
  • boolean[][] visited: 방문 여부를 나타내는 2차원 배열입니다. 각 좌표를 방문했는지 여부가 저장됩니다.

• 로직

  • 입력을 받고, 보물섬 지도를 arr 배열에 저장합니다.
  • 모든 좌표를 순회하면서 L인 지점을 찾습니다.
  • L인 지점을 찾을 때마다 해당 좌표를 시작으로 BFS 탐색을 진행합니다.
  • BFS 탐색은 큐를 이용하여 상하좌우로 이동하면서 L인 지점을 찾고, 이동 거리를 계산합니다.
  • BFS 탐색 중에 최대 이동 거리인 max_distance를 업데이트합니다.
  • 모든 좌표에 대한 BFS 탐색이 끝나면, 최대 이동 거리인 max_distance를 출력합니다.

이 코드는 주어진 보물섬 지도에서 L로 표시된 지점들 사이의 최장 거리를 구하는 문제를 해결하는데 활용됩니다.

자바스크립트

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

const dy = [-1, 1, 0, 0];
const dx = [0, 0, -1, 1];
let maxDist = 0;

function bfs(sy, sx, arr, row, col) {
  const queue = [];
  queue.push([sy, sx]);

  const distance = Array.from(Array(row), () => Array(col).fill(-1));
  const visited = Array.from(Array(row), () => Array(col).fill(false));

  visited[sy][sx] = true;
  distance[sy][sx] = 0;
  let maxDistance = 0;

  while (queue.length > 0) {
    const [y, x] = queue.shift();

    for (let d = 0; d < 4; d++) {
      const ny = y + dy[d];
      const nx = x + dx[d];

      if (ny >= 0 && ny < row && nx >= 0 && nx < col && !visited[ny][nx] && arr[ny][nx] === 1) {
        visited[ny][nx] = true;
        queue.push([ny, nx]);
        distance[ny][nx] = distance[y][x] + 1;
        if (distance[ny][nx] > maxDistance) {
          maxDistance = distance[ny][nx];
        }
      }
    }
  }

  return maxDistance;
}

rl.on('line', (line) => {
  const [row, col] = line.split(' ').map(Number);
  const arr = [];

  rl.on('line', (line) => {
    const rowArr = [];
    for (let j = 0; j < col; j++) {
      const c = line.charAt(j);
      if (c === 'L') {
        rowArr.push(1);
      } else {
        rowArr.push(0);
      }
    }
    arr.push(rowArr);
  }).on('close', () => {
    for (let i = 0; i < row; i++) {
      for (let j = 0; j < col; j++) {
        if (arr[i][j] === 1) {
          const dist = bfs(i, j, arr, row, col);
          if (maxDist < dist) {
            maxDist = dist;
          }
        }
      }
    }

    console.log(maxDist);
  });
});

파이썬

from collections import deque

dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
max_dist = 0

def bfs(sy, sx, arr, row, col):
    queue = deque()
    queue.append((sy, sx))

    distance = [[-1] * col for _ in range(row)]
    visited = [[False] * col for _ in range(row)]

    visited[sy][sx] = True
    distance[sy][sx] = 0
    max_distance = 0

    while queue:
        y, x = queue.popleft()

        for d in range(4):
            ny = y + dy[d]
            nx = x + dx[d]

            if 0 <= ny < row and 0 <= nx < col and not visited[ny][nx] and arr[ny][nx] == 1:
                visited[ny][nx] = True
                queue.append((ny, nx))
                distance[ny][nx] = distance[y][x] + 1
                if distance[ny][nx] > max_distance:
                    max_distance = distance[ny][nx]

    return max_distance


row, col = map(int, input().split())

arr = []
for _ in range(row):
    line = input().rstrip()
    row_arr = [1 if c == 'L' else 0 for c in line]
    arr.append(row_arr)

for i in range(row):
    for j in range(col):
        if arr[i][j] == 1:
            dist = bfs(i, j, arr, row, col)
            if max_dist < dist:
                max_dist = dist

print(max_dist)