문제 링크
https://www.acmicpc.net/problem/2589
문제 풀이
보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 문제이다.
최단 거리에 대한 조건은 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳이라고 명시되어 있다.
이 말은 최단 거리들 중에서 가장 시간이 오래 걸리는 두 점을 찾으라는 말이며 위치로 본다면 최단 거리들 중에서 가장 먼 거리를 구하라는 말이다.
문제에서 최단 거리들 중에서 가장 시간이 오래 걸린다는 말은 두 점 간의 최단 거리는 여러 개가 존재할 수 있고 그 중에서 가장 거리가 먼 두 점을 찾으라는 말로 해석하면 된다.
예시
그림을 통해 지도 내 존재하는 어떤 한 점에서 다른 점까지의 최단 거리들의 존재를 확인할 수 있다.
파란색 점들은 시작 점에서 이동할 수 있는 지점들이며 그 중에 최대한 먼 거리가 또 다른 주황색 점이다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
private static int rowSize;
private static int colSize;
private static int[][] map;
private static int[] dx = new int[]{0, 0, 1, -1};
private static int[] dy = new int[]{1, -1, 0, 0};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
rowSize = Integer.parseInt(st.nextToken());
colSize = Integer.parseInt(st.nextToken());
map = new int[rowSize][colSize];
for (int i = 0; i < rowSize; i++) {
String[] row = br.readLine().split("");
for (int j = 0; j < colSize; j++) {
String value = row[j];
if (value.equals("L")) {
map[i][j] = 1;
}
}
}
int answer = 0;
for (int i = 0; i < rowSize; i++) {
for (int j = 0; j < colSize; j++) {
if (map[i][j] == 1) {
boolean[][] visited = new boolean[rowSize][colSize];
int maxDistance = search(i, j, visited);
answer = Math.max(maxDistance, answer);
}
}
}
System.out.println(answer);
br.close();
}
public static int search(int row, int col, boolean[][] visited) {
Queue<Coordinate> queue = new LinkedList<>();
queue.offer(new Coordinate(row, col,0));
visited[row][col] = true;
int maxDist = 0;
while (!queue.isEmpty()) {
Coordinate current = queue.poll();
if(maxDist < current.getDist()){
maxDist = current.getDist();
}
for (int i = 0; i < 4; i++) {
int nRow = current.getRow() + dx[i];
int nCol = current.getCol() + dy[i];
if(isIn(nRow, nCol) && map[nRow][nCol]==1 && !visited[nRow][nCol] ){
visited[nRow][nCol] = true;
queue.offer(new Coordinate(nRow, nCol, current.getDist()+1));
}
}
}
return maxDist;
}
private static boolean isIn(int row, int col) {
return (0 <= row && row < rowSize) && (0 <= col && col < colSize);
}
}
class Coordinate {
private final int row;
private final int col;
private final int dist;
public Coordinate(int row, int col, int dist) {
this.row = row;
this.col = col;
this.dist = dist;
}
public int getRow() {
return row;
}
public int getCol() {
return col;
}
public int getDist() {
return dist;
}
'코딩테스트 > boj' 카테고리의 다른 글
| 줄어들지 않아 - 백준 2688 (0) | 2024.05.22 |
|---|---|
| 떡 먹는 호랑이 - 백준 2502 자바 (0) | 2024.05.22 |
| 별 찍기 11 - 2448 (0) | 2024.03.30 |
| 벽 부수고 이동하기 - 백준 2206 (0) | 2024.03.30 |
| 램프 - 백준 1034 (0) | 2024.03.07 |
