[BFS] 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유( 백준 17129번, 자바)

 

17129번: 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유 (acmicpc.net)

17129번: 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유

 

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	static int[] dx= {0,1,0,-1};
	static int[] dy= {1,0,-1,0};
	static boolean[][] visit;
	static int n,m;
	static Queue<int[] > q;
	static char[][] c;
	static StringBuilder sb;
	
	public static void main(String[] args) throws Exception{
		
		Scanner sc=new Scanner(System.in);
		
		n=sc.nextInt();
		m=sc.nextInt();
		
		q=new LinkedList<>();
		visit=new boolean[n][m];
		sb=new StringBuilder("");
		c=new char[n][m];
		for(int i=0;i<n;i++) {
			String s=sc.next();
			c[i]=s.toCharArray();
		}
		
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				if(c[i][j]=='2') bfs(i,j,1);
			}
		}
		if(sb.toString().equals("")) sb.append("NIE");
		System.out.println(sb.toString());
	}
	
	static void bfs(int a, int b, int cc) {
		q.add(new int[] {a,b,cc});
		
		while(!q.isEmpty()) {
			int[] x=q.poll();
			
			for(int i=0;i<4;i++) {
				int nx=x[0]+dx[i];
				int ny=x[1]+dy[i];
				
				
				if(nx<0 || nx>=n || ny<0 || ny>=m  || visit[nx][ny] || c[nx][ny]=='1') continue;
				
				if(c[nx][ny]=='3'|| c[nx][ny]=='4'|| c[nx][ny]=='5') {
					sb.append("TAK\n");
					sb.append(x[2]);
					return;
				}
				visit[nx][ny]=true;
				q.add(new int[] {nx,ny,x[2]+1});
				
			}
		}
	}

}