[BOJ 5427] ํ์ถ
1. ๋ฌธ์ : https://www.acmicpc.net/problem/3055
2. ํ์ด
bfs ๋ฌธ์ ๋คํํ ์ ํ์๋ค
ํ๋ฅผ ์ฌ์ด์ฆ๋ก ๋ฐ๋ณต๋ฌธ ๋๋ฉฐ ๊ด๋ฆฌํ๋ฉด ์ฌ์ (๊ตณ์ด water์ -1 ๋ฃ์ ํ์ X)
3. ์ฝ๋
import java.util.*;
public class Main {
static int R,C;
static char map[][];
static Queue<Point> water = new LinkedList<>();
static int ddx[] = {-1,1,0,0};
static int ddy[] = {0,0,-1,1};
static int dx = 0, dy = 0;
static boolean visited[][];
static int cnt = 0;
static boolean flag = false;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
R = sc.nextInt();
C = sc.nextInt();
map = new char[R][C];
visited = new boolean[R][C];
int sx = 0, sy = 0;
for(int i=0; i<R; i++){
String temp = sc.next();
for(int j=0; j<C; j++){
map[i][j] = temp.charAt(j);
if(map[i][j] == '*'){
water.offer(new Point(i,j));
}else if(map[i][j] == 'S'){
sx = i;
sy = j;
}else if(map[i][j] == 'D'){
dx = i;
dy = j;
}
}
}
bfs(sx,sy);
if(!flag) System.out.println("KAKTUS");
else System.out.println(cnt);
}
static void bfs(int x, int y){
Queue<Point> queue = new LinkedList<>();
queue.offer(new Point(-1,-1));
queue.offer(new Point(x,y));
visited[x][y] = true;
Loop1:
while(!queue.isEmpty()){
Point cur = queue.poll();
if(cur.x == -1){
cnt++;
if(!water.isEmpty()){
water.offer(new Point(-1,-1));
flood();
}
if(!queue.isEmpty()){
queue.offer(new Point(-1,-1));
}
continue;
}
for(int i=0; i<4; i++){
int nx = cur.x + ddx[i];
int ny = cur.y + ddy[i];
if(nx<0 || ny<0 || nx>=R || ny>=C) continue;
if(visited[nx][ny]) continue;
if(map[nx][ny] == '*' || map[nx][ny] == 'X') continue;
if(map[nx][ny] == 'D') {
flag = true;
break Loop1;
}
queue.offer(new Point(nx,ny));
visited[nx][ny] = true;
}
}
}
static void flood(){
while(!water.isEmpty()){
Point cur = water.poll();
if(cur.x == -1) break;
for(int i=0; i<4; i++){
int nx = cur.x + ddx[i];
int ny = cur.y + ddy[i];
if(nx<0 || ny<0 || nx>=R || ny>=C) continue;
if(map[nx][ny] == '.'){
map[nx][ny] = '*';
water.offer(new Point(nx,ny));
}
}
}
}
static class Point {
int x, y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}
'๐ป Coding Problems Solving > DFS | BFS | Backtracking' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[ํ๋ก๊ทธ๋๋จธ์ค] ๋ฆฌ์ฝ์ณ ๋ก๋ด (์๋ฐ java) (0) | 2023.12.01 |
---|---|
[BOJ 5427] ๋ถ (0) | 2023.08.24 |
[BOJ 2206] ๋ฒฝ๋ถ์๊ณ ์ด๋ํ๊ธฐ (0) | 2023.08.21 |
[BOJ 16234] ์ธ๊ตฌ์ด๋ (0) | 2023.08.17 |
[BOJ 1103] ์คํํธ๋งํฌ (0) | 2023.08.11 |
์ต๊ทผ๋๊ธ