BOJ - 25307 ) 시루의 백화점 구경

---

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

25307번: 시루의 백화점 구경

 

---

첫 시작점으로 부터 목적지(2) 까지 갈 수 있는지 확인한다 (bfs)

탐색전 마네킹거리(K, 마네킹 좌표에서 bfs로 k번이동하여 갈수있는곳)를 불가능 표시를 해두고

 

한번만 BFS를 진행하면 해결된다.

---

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class BOJ_25307 {
	
	
	public static boolean inRange(int yy, int xx, int n , int m) {return yy<n&&xx<m&&yy>=0&&xx>=0;}
	
	public static void main(String[] args) throws IOException {

			
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		

		ArrayDeque<int[]> dq = new ArrayDeque<>();
		ArrayList<int[]> node = new ArrayList<>();
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		

		int dir[][] = {{1,0},{-1,0},{0,1},{0,-1}};
 		int map[][] = new int[n][m];
		int sx= 0;
		int sy= 0;
		int ex= -987654321;
		int ey= -987654321;
		
		for(int i=0;i<n;++i) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<m;++j) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] ==4) {sx=j;sy=i;} 
				if(map[i][j] ==2) {ex=j;ey=i;} 
				if(map[i][j] ==3) {node.add(new int[] {i,j});
				} 
			}
		}
		
		
		int size = node.size();
	
		for(int aa=0;aa<size;aa++) {
		    int i = node.get(aa)[0];
		    int j = node.get(aa)[1];
			
			dq.add(new int[] {i,j});
			map[i][j]=1;
			
			while(!dq.isEmpty()) {
				
				int now[] =dq.poll();
					for(int a=0;a<4;a++) {
						int nexty=now[0]+dir[a][0];
						int nextx=now[1]+dir[a][1];
						if(inRange(nexty,nextx,n,m)&&map[nexty][nextx]!=1&&dist(nexty,nextx,i,j,k)) {
							map[nexty][nextx]=1;
							dq.add(new int[] {nexty,nextx});
						}
					}
			}
		}
		
		
		
        int answer= 987654321;
		
		dq.add(new int[] {sy,sx,0});
		map[sy][sx] = 5; 
		
		top:
		while(!dq.isEmpty()) {
			int now[] = dq.poll();
			for(int a=0;a<4;a++) {
				
				int nexty=now[0]+dir[a][0];
				int nextx=now[1]+dir[a][1];
				
				if(inRange(nexty,nextx,n,m)
						&&map[nexty][nextx]<5
						  &&map[nexty][nextx]!=1
						     ) {
					
					if(map[nexty][nextx]==2) {
						answer = answer > now[2]+1 ? now[2]+1 : answer;
						break top;
				    }
					dq.add(new int[] {nexty,nextx,now[2]+1});
					map[nexty][nextx]=5;
				}
			}
		}
		
		System.out.println( answer==987654321 ? -1 : answer );

	
		
		
	}

	private static boolean dist(int nexty, int nextx, int i, int j, int k) {
		
		return (Math.abs(nextx-j)+Math.abs(nexty-i)) <=k;
	}

	
}

---