728x90
<🔗문제 링크>
https://www.acmicpc.net/problem/2589
2589번: 보물섬
보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서
www.acmicpc.net
<✏️문제풀이>
input 저장 시 map에 'L'인 경우 true를 저장 , 'W'인 경우 false를 저장하였습니다.
이문제의 포인트는 한 땅에서 가장 멀리 있는 두 육지를 찾고 두 육지의 까지의 시간을 출력하는 것이라 생각했습니다.
하지만 한 지점에서부터 탐색을 한경우에는 땅이 여러 개인 경우, 가장 긴 두 육지의 시작 노드가 아닌 경우 등 최대 값을 보장할 수 없습니다.
따라서 모든 땅인 지점에서부터 너비 우선 탐색을 하여서 가장 긴 노드를 탐색하여 최댓값을 출력하였습니다.
최댓값을 저장하기 위해서는 visit을 int형 배열로 선언하여 움직일 때마다 +1 하여 저장하도록 하여서 최댓값을 찾았습니다.
<📝코드>
import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static int row, col;
private static boolean[][] map;
private static int[][] visited;
private static List<Integer> dirx = List.of(-1, 1, 0, 0);
private static List<Integer> diry = List.of(0, 0, -1, 1);
public static void main(String[] args) throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
row = Integer.parseInt(st.nextToken());
col = Integer.parseInt(st.nextToken());
map = new boolean[row][col]; //true-> land, false -> water
saveInput();
System.out.println(scanMap());
}
private static int scanMap() {
int max = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
//땅인 경우만 탐색
if (map[i][j]) max = Math.max(max, bfs(i, j));
}
}
return max;
}
private static int bfs(int x, int y) {
visited = new int[row][col];
int max = 0;
Queue<Point> q = new LinkedList<>();
q.add(new Point(x, y));
visited[x][y] = 1;
while (!q.isEmpty()) {
Point now = q.poll();
max = Math.max(max, visited[now.x][now.y]);
for (int i = 0; i < 4; i++) {
int mvx = now.x + dirx.get(i);
int mvy = now.y + diry.get(i);
//벗어남
if (mvx >= map.length || mvx < 0 || mvy < 0 || mvy >= map[0].length) continue;
//땅이고, 방문 안된 노드이면
if (map[mvx][mvy] && visited[mvx][mvy] == 0) {
visited[mvx][mvy] = visited[now.x][now.y] + 1;
q.add(new Point(mvx, mvy));
}
}
}
return max - 1;
}
private static void saveInput() throws IOException {
for (int i = 0; i < row; i++) {
char[] temp = br.readLine().toCharArray();
for (int j = 0; j < col; j++) {
char input = temp[j];
boolean saveInput = false;
if (input == 'L') saveInput = true; //땅인 경우만 true 리턴
map[i][j] = saveInput;
}
}
}
}
728x90
'알고리즘' 카테고리의 다른 글
[백준 Java] 2812 크게만들기 그리디 알고리즘 (0) | 2022.11.10 |
---|---|
[백준 Java]1717 집합의 표현 (0) | 2022.11.09 |
[백준 JAVA] 7562 나이트의 이동, BFS(너비 우선 탐색) (0) | 2022.11.06 |
[백준 JAVA] 11561 N과 M(3) 백트랙킹 (0) | 2022.11.06 |
이진탐색(binary search) (0) | 2022.11.05 |
댓글