알고리즘/백준
[Java] BOJ 2589번 보물섬
컴공맨
2021. 6. 11. 15:47
2589번: 보물섬
첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의
www.acmicpc.net
풀이
BFS를 이용하여 해결했습니다.
이때, 문제의 조건에 맞추기 위해 지도에서 'L'인 모든 점에 대해서 BFS를 수행하고 그때의 최대 거리를 계속 갱신해야 합니다.
코드
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 {
public static class Info {
int y, x;
public Info(int y, int x) {
super();
this.y = y;
this.x = x;
}
}
public static int N, M, answer;
public static int[] dy = {-1, 1, 0, 0};
public static int[] dx = {0, 0, -1, 1};
public static boolean[][] visited;
public static char[][] map;
public static int[][] distMap;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new char[N][M];
for (int i = 0; i < N; ++i) {
map[i] = br.readLine().toCharArray();
}
for (int i = 0 ; i < N; ++i) {
for (int j = 0; j < M; ++j) {
visited = new boolean[N][M];
distMap = new int[N][M];
if (map[i][j] == 'L' & !visited[i][j]) {
bfs(i, j);
calc();
}
}
}
System.out.println(answer);
}
public static void bfs(int y, int x) {
Queue<Info> q = new LinkedList<Info>();
q.offer(new Info(y, x));
visited[y][x] = true;
while (!q.isEmpty()) {
Info info = q.poll();
for (int i = 0; i < 4; ++i) {
int ny = info.y + dy[i];
int nx = info.x + dx[i];
if (ny < 0 || nx < 0 || ny >= N || nx >=M) {
continue;
}
if (!visited[ny][nx] && map[ny][nx] == 'L') {
distMap[ny][nx] = distMap[info.y][info.x] + 1;
q.offer(new Info(ny, nx));
visited[ny][nx] = true;
}
}
}
}
public static void calc() {
for (int i = 0 ; i < N; ++i) {
for (int j = 0; j < M; ++j) {
answer = (answer < distMap[i][j]) ? distMap[i][j] : answer;
}
}
}
}
pyo7410/Algorithm
1일 1커밋을 목표로! Contribute to pyo7410/Algorithm development by creating an account on GitHub.
github.com