백준 3055 탈출

https://www.acmicpc.net/problem/3055

3055번: 탈출

0. 큐::x,y,경과시간

 

1. '*'들의 좌표를 qWater에 넣기

2. 'S'의 좌표를 qGo에 넣기

3. D의 좌표를 target에 저장

// 입력끝

 

4.bfs

bfs

 

4-0: 물큐를 먼저 실행 & 고슴도치를 나중에 이동 => 물이갈 예정인곳은 못간다 구현. 

4-1:물큐가 안빔 or 고슴도치큐가 안비면 무한반복 (물큐가 먼저 빈경우에도 qSize만큼 돔 => 자동스킵됨)

4-2:물: 상하좌우탐색, 빈땅(.) and 미방문 ->  맵을 물(*)로 바꿔주기, 큐에추가,  방문처리

4-3고슴도치 : 상하좌우탐색, 빈땅(.) or 비버(D) and 미방문 ->  맵을 고슴도치(S)로 바꿔주기, 큐에추가(좌표,부모시간+1),  방문처리

4-4고슴도치 : 탐색할노드가 타겟(비버)이면 잘도착했음-> 그때 좌표,시간 리턴, 출력 , 종료

4-5:위의 리턴이안됨 -> 비버에 갈수없음 -> KACTUS출력, 종료

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_3055_유동훈 {
	static int R;
	static int C;
	static char[][] map;
	static Queue<int[]> qWater = new LinkedList<>();
	static Queue<int[]> qGo = new LinkedList<>();
	static int[] dr= {-1,1,0,0};
	static int[] dc= {0,0,-1,1};
	static boolean[][] visit;
	static int targetX;
	static int targetY;
	
	static void print()
	{
		for(int i=0;i<R;++i)
		{
			//st = new StringTokenizer(br.readLine());
			for(int j=0;j<C;++j)
			{
				System.out.print(map[i][j]);
			}
			System.out.println();
		}
	}
	
	static int[] bfs()
	{
		int[] node = qWater.peek();
		
		while(!qWater.isEmpty() || !qGo.isEmpty())
		{
			//레벨별 실행
			int qSizeWater=qWater.size();
			for(int i=0;i<qSizeWater;++i)
			{
				node = qWater.poll();
				
				//노드의 상,하,좌,우 탐색
				for(int j=0;j<4;++j)
				{
					int nr=node[0]+dr[j];
					int nc=node[1]+dc[j];
					
					if(nr>=0 && nr<R && nc>=0 && nc<C)
					{
						if(map[nr][nc]=='.' && !visit[nr][nc])
						{
							map[nr][nc]='*';
							qWater.add(new int[] {nr,nc,-1});
							visit[nr][nc]=true;
						}
					}
				}
			}
			
			//레벨별 실행
			int qSizeGo=qGo.size();
			for(int i=0;i<qSizeGo;++i)
			{
				node = qGo.poll();
				
				if(node[0]==targetX && node[1]==targetY) return node;
				
				//노드의 상,하,좌,우 탐색
				for(int j=0;j<4;++j)
				{
					int nr=node[0]+dr[j];
					int nc=node[1]+dc[j];
					
					if(nr>=0 && nr<R && nc>=0 && nc<C)
					{
						if(map[nr][nc]=='.' || map[nr][nc]=='D' && !visit[nr][nc])
						{
							map[nr][nc]='S';
							qGo.add(new int[] {nr,nc,node[2]+1});
							visit[nr][nc]=true;
						}
					}
				}
			}
            
            //한 레벨끝!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
            
		} //다음레벨
       
		
		//D에 도달할수없음
		return new int[] {999,999,999};
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		//StringBuilder sb=new StringBuilder();
		StringTokenizer st;
		st=new StringTokenizer(br.readLine());
		R=Integer.parseInt(st.nextToken());
		C=Integer.parseInt(st.nextToken());
		
		map=new char[R][C];
		visit= new boolean[R][C];
		Queue<int[]> qTemp = new LinkedList<>();
		for(int i=0;i<R;++i)
		{
			StringBuilder sb=new StringBuilder();
			sb.append(br.readLine());
			for(int j=0;j<C;++j)
			{
				map[i][j]=sb.charAt(j);
				if(map[i][j]=='*') qWater.offer(new int[] {i,j,-1});
				if(map[i][j]=='S') qGo.offer(new int[] {i,j,0});
				if(map[i][j]=='D') {targetX=i; targetY=j;}
			}
		}
		
		//------------------입력끝-----------------------

		//큐:x,y,시간
		
		//print();
		int[] result=bfs();
		if(result[0]==999) System.out.println("KAKTUS");
		else System.out.println(result[2]);
	}

}