접근
전형적인 BFS 문제였다. 가로 세로의 길이가 50 이하로, 모든 경우를 탐색한다 해도 2500번만 보면 된다. 모든 칸을 탐색하며 육지일 경우 bfs로 가장 긴 거리를 리턴하고, 그 중 가장 큰 수를 출력하면 된다.
개인적으로 하나로 연결된 육지를 계속해서 확인해봐야 한다는 점이 비효율적으로 느껴져 개선 방안을 찾아보고자 했지만.. 다른 사람들의 풀이를 참고해봐도 실행 시간이 비슷한 것으로 보아 특별한 해결책은 찾지 못했다.
코드
import java.util.*;
import java.lang.*;
import java.io.*;
class Main {
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static char[][] map;
public static class Pos{
int x;
int y;
int dist = 0;
Pos(int x, int y, int d){
this.x = x;
this.y = y;
this.dist = d;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// 입력값 저장
int h = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
map = new char[h][w];
for(int i = 0; i < h;i++)
map[i] = br.readLine().toCharArray();
// 최단거리 계산
int answer = solve(w, h);
System.out.println(answer);
}
public static int solve(int w, int h){
int res = 0;
for(int i = 0;i < h;i++){
for(int j = 0;j < w;j++){
if(map[i][j] =='W') continue;
int curMax = bfs(i, j, w, h);
res = Math.max(res, curMax);
}
}
return res;
}
public static int bfs(int x, int y, int w, int h){
int maxDist = 0;
boolean[][] visit = new boolean[h][w];
for(int i = 0;i < h;i++)
Arrays.fill(visit[i], false);
Queue<Pos> q = new LinkedList();
q.add(new Pos(x, y, 0));
visit[x][y] = true;
while(!q.isEmpty()){
Pos cur = q.poll();
maxDist = Math.max(maxDist, cur.dist);
for(int d = 0;d < 4;d++){
int nx = cur.x + dx[d];
int ny = cur.y + dy[d];
// 범위를 벗어남
if(!inBound(nx, ny, w, h)) continue;
// 바다이거나 이미 방문함
if(map[nx][ny] == 'W' || visit[nx][ny]) continue;
q.add(new Pos(nx, ny, cur.dist+1));
visit[nx][ny] = true;
}
}
return maxDist;
}
public static boolean inBound(int x, int y, int w, int h){
return !(x < 0 || x >= h || y < 0 || y >= w);
}
}
'Algorithm' 카테고리의 다른 글
| [백준] 5430: AC JAVA (0) | 2025.05.18 |
|---|---|
| [백준] 1092: 배 JAVA (0) | 2025.03.02 |
| [백준] 1976: 여행 가자 JAVA (0) | 2025.03.01 |
| [백준] 11403: 경로 찾기 JAVA (0) | 2025.02.28 |
| [백준] 9084: 동전 JAVA (0) | 2025.02.14 |
