문제
https://www.acmicpc.net/problem/3055
풀이
하나의 지도 배열에 BFS가 두 번 쓰이는 문제입니다. 전형적인 BFS 문제에 물이 퍼지는 것을 고려해야하는 문제입니다.
특정 좌표에 몇 초 후에 물이 도달하는 지는 BFS를 통해 미리 구할 수 있습니다. time[][] 이라는 배열을 선언하여, 물이 미래에 도착할 시간을 저장하고, 고슴도치의 시간(depth)와 물이 도착하는 시간(time[][])을 비교해 문제를 해결했습니다.
소스코드
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int N,M;
static char[][] map;
static int[][] time;
static boolean[][] visited;
static boolean[][] visited1;
static int[] dr = {-1,1,0,0};
static int[] dc = {0,0,-1,1};
static Queue<int[]> queue = new LinkedList<>();
static Queue<int[]> waters = new LinkedList<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
map = new char[N][M];
visited = new boolean[N][M];
visited1 = new boolean[N][M];
time = new int[N][M];
for(int r=0;r<N;r++){
String str = sc.next();
for(int c=0;c<M;c++){
time[r][c] = 2500;
map[r][c] = str.charAt(c);
if(map[r][c] == 'S'){
queue.add(new int[]{r,c,1});
visited[r][c] = true;
}
if(map[r][c]=='*'){
waters.add(new int[]{r,c,1});
time[r][c] = -1;
}
}
}
waterCheck();
int ans = bfs();
if(ans==-1) System.out.println("KAKTUS");
else System.out.println(ans-1);
}
static int bfs(){
while(!queue.isEmpty()){
int[] info = queue.poll();
int r = info[0];
int c = info[1];
int depth = info[2];
if(map[r][c]=='D'){
return depth;
}
for(int i = 0; i<4;i++){
int idr = r+dr[i];
int idc = c+dc[i];
if(idr<0||idc<0||idr>=N||idc>=M) continue;
if(visited[idr][idc]) continue;
if(map[idr][idc]=='*'||map[idr][idc]=='X') continue;
if(depth<time[idr][idc]) {
visited[idr][idc] = true;
queue.add(new int[]{idr, idc, depth + 1});
}
}
}
return -1;
}
static void waterCheck(){
while(!waters.isEmpty()){
int[] info = waters.poll();
int r = info[0];
int c = info[1];
int depth = info[2];
for(int i = 0; i<4;i++){
int idr = r+dr[i];
int idc = c+dc[i];
if(idr<0||idc<0||idr>=N||idc>=M) continue;
if(visited1[idr][idc]) continue;
if(map[idr][idc]=='D'||map[idr][idc]=='X') continue;
if(map[idr][idc]=='.'||map[idr][idc]=='S'){
visited1[idr][idc] = true;
time[idr][idc] = depth;
waters.add(new int[]{idr,idc,depth+1});
}
}
}
}
}
'Java > BOJ' 카테고리의 다른 글
[BOJ] 백준 25195. Yes or yes (0) | 2024.02.26 |
---|---|
[BOJ] 백준 2573. 빙산 (0) | 2024.02.22 |
[BOJ] 백준 11054. 가장 긴 바이토닉 부분 수열 (0) | 2024.02.21 |
[BOJ] 백준 10610. 30 (0) | 2024.02.20 |
[BOJ] 백준 1238. 파티 (0) | 2024.01.20 |