https://www.acmicpc.net/problem/3055
3055번: 탈출
사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제
www.acmicpc.net
분류 : BFS , 시뮬레이션
더보기
import java.io.*;
import java.math.*;
import java.util.*;
class Myscanner{
BufferedReader br;
StringTokenizer st;
public Myscanner(){
br = new BufferedReader(new InputStreamReader(System.in));
}
String next(){
while(st == null|| !st.hasMoreElements()){
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt(){
return Integer.parseInt(next());
}
long nextLong(){
return Long.parseLong(next());
}
double nextDouble(){
return Double.parseDouble(next());
}
}
public class Main {
public static Myscanner sc = new Myscanner();
static int N,M,DX,DY,inf = Integer.MAX_VALUE;
static char[][] forest;
static int[][] biber,flood;
static int[] dx = {-1,0,1,0};
static int[] dy = {0,-1,0,1};
public static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
public static void main(String[] args) throws IOException {
N = sc.nextInt();
M = sc.nextInt();
forest = new char[N][M];
biber = new int[N][M];
flood = new int[N][M];
Queue<Point> b = new LinkedList<>();
Queue<Point> w = new LinkedList<>();
for(int i=0;i<N;i++)
{
forest[i] = sc.next().toCharArray();
}
for(int i=0;i<N;i++)
{
for(int j=0;j<M;j++)
{
flood[i][j]=inf;
if(forest[i][j]=='S'){
b.offer(new Point(i,j));
biber[i][j]=1;
}
else if(forest[i][j]=='*')
{
w.offer(new Point(i,j));
flood[i][j] =1;
}
}
}
wfs(w);
int minute = bfs(b);
if(minute == -1){
out.println("KAKTUS");
}
else{
out.println(minute);
}
out.flush();
}
private static void wfs(Queue<Point> w) {
while(!w.isEmpty())
{
int size = w.size();
for(int sz = 0; sz<size;sz++)
{
Point p = w.poll();
int x = p.x;
int y = p.y;
for(int ar =0;ar<4;ar++)
{
int cx = x+dx[ar];
int cy = y+dy[ar];
if(cx>=0 && cx<N && cy>=0 && cy<M)
if(forest[cx][cy]!='X' && forest[cx][cy]!='D' && flood[cx][cy]==inf)
{
flood[cx][cy] = Math.min(flood[x][y]+1,flood[cx][cy]);
w.offer(new Point(cx,cy));
}
}
}
}
}
private static int bfs(Queue<Point> b) {
int seconds=1;
while(!b.isEmpty())
{
int size = b.size();
for(int sz = 0; sz<size;sz++)
{
Point p = b.poll();
int x = p.x;
int y = p.y;
for(int ar =0; ar<4;ar++)
{
int cx = x+dx[ar];
int cy = y+dy[ar];
if(cx>=0 && cx<N && cy>=0 && cy<M){
if(forest[cx][cy]!='X' && flood[cx][cy]>biber[x][y]+1 && biber[cx][cy]==0 && forest[cx][cy]!='D')
{
biber[cx][cy]=biber[x][y]+1;
b.offer(new Point(cx,cy));
}
else if(forest[cx][cy]=='D'){
return seconds;
}
}
}
}
seconds++;
}
return -1;
}
}
class Point{
int x,y;
public Point(int x, int y){
this.x = x;
this.y = y;
}
}
내가 풀었던 불 문제나 다른 문제와 비슷한 형태의 bfs 문제이다.
물이 다른 곳으로 이동할 때의 걸리는 시간보다 고슴도치가 더 빨리 움직여 비버의 굴로 도착할 수 있는가 없는가를 해결하는 문제..
처음에 쓸데 없이 이상한 코드를 집어넣어서 시간 초과가 나왔고 지속적으로 수정하여 해결 완료
'PS' 카테고리의 다른 글
[BOJ]11723번 : 집합 (0) | 2017.04.03 |
---|---|
[BOJ]2206번 : 벽 부수고 이동하기 (0) | 2017.04.02 |
[BOJ]1194번 : 달이 차오른다, 가자. (0) | 2017.03.31 |
[BOJ]5427번 : 불 (0) | 2017.03.31 |
[BOJ]4179번 : Fire! (0) | 2017.03.31 |