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)