문제풀이/백준
[백준]2589: 보물섬 - JAVA
빈둥벤둥
2021. 3. 2. 15:34
[백준]2589: 보물섬
2589번: 보물섬
보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서
www.acmicpc.net
풀이
최단거리 중에서의 최대값을 구하는 문제였다. BFS로 각 정점에서의 최단 거리를 구해주고 그 최단 거리 들 중의 최대값을 계산해 주었다.
BFS에서 현재 위치와 현재 위치 까지의 거리를 저장해줄 Node class를 만들어서 저장해 주었다.
그리고 이중 for문으로 모든 노드를 확인하면서 '육지'인 경우에만 BFS탐색을 하도록 하였다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
import java.util.*;
public class Main {
static int[] dx = {0, 1, 0, -1};
static int[] dy = {1, 0, -1, 0};
static char[][] board;
static int n, m;
static boolean[][] visited;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
scan.nextLine();
board = new char[n][m];
for(int i = 0; i < n; i++) {
String str = scan.nextLine();
for(int j = 0; j < m; j++) {
board[i][j] = str.charAt(j);
}
}
int max = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(board[i][j] == 'L') {
visited = new boolean[n][m];
int len = bfs(i, j);
max = Math.max(max, len);
}
}
}
System.out.println(max);
}
public static int bfs(int x, int y) {
Queue<Node> q = new LinkedList<>();
q.offer(new Node(x, y, 0));
visited[x][y] = true;
int len = 0;
while(!q.isEmpty()) {
Node current = q.poll();
for(int i = 0; i < 4; i++) {
int nx = current.x + dx[i];
int ny = current.y + dy[i];
if(nx >= 0 && ny >= 0 && nx < n && ny < m) {
if(visited[nx][ny] == false && board[nx][ny] == 'L') {
q.offer(new Node(nx, ny, current.cost + 1));
len = Math.max(len, current.cost + 1);
visited[nx][ny] = true;
}
}
}
}
return len;
}
public static class Node {
int x;
int y;
int cost;
public Node(int x, int y, int cost) {
this.x = x;
this.y = y;
this.cost = cost;
}
}
}
|
cs |