[백준] 17129 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유

문제 출처: www.acmicpc.net/problem/17129

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

: 우선 딱따구리 이름이 굉장히 길어서 조금 보기 힘들지만 사실 별 특이한건 없다.

: 딱따구리 가족이 가장 빠르게 음식에 도달하는 거리를 찾는 것이다.

: 어떤 음식이든 상관없이 하나에라도 도달하면 되기 때문에 음식을 구별해줄 필요는 없다.

 

: BFS 방식으로 접근할 수 있는데, 벽일 때 즉 값이 1일 때와 범위를 벗어날 때 그리고 이미 갔던 곳만 제외하고 탐색할 수 있도록 한다.

: 만약 새롭게 탐색한 곳에 음식이 있다면 그 즉시 탐색을 멈추고 그 때까지 걸렸던 거리를 반환해 준다.

: 만약 while문 중간에 멈추지 않고 끝까지 모두 탐색한 경우는 음식에 도달할 수 없는 경우이기 때문에 구별해주기 위해 -1을 반환하도록 한다.

: 그 후 main 메소드로 돌아와서 return 값이 -1일 때 즉, 음식에 도달할 수 없을 때와

: return이 -1이 아닐 때 즉, 음식에 도달할 경우를 나눠 출력형식에 맞춰 출력해준다.

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 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int N, M;
	static int[][] map;
	static boolean[][] v;
	public static void main(String[] args) throws IOException {
		// 행렬의 크기 N과 M을 입력받고
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		// 행렬을 만든 후
		map = new int[N][M];
		v = new boolean[N][M];
		
		int r = -1, c = -1;
		// 행렬의 값을 입력받으면서
		for(int i = 0; i < N; i++) {
			String[] tmp = br.readLine().split("");
			for(int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(tmp[j]);
				// 식구 즉, 2인 곳의 행과 열을 따로 저장해놓고
				if(map[i][j] == 2) {
					r = i;
					c = j;
				} 
			}
		}
		// bfs 방식으로 접근
		int ans = bfs(r, c);
		if(ans == -1) {
			System.out.println("NIE");
		}else {
			System.out.println("TAK\n"+ans);
		}
	}
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
	private static int bfs(int r, int c) {
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] {r, c, 0});
		
		while(!q.isEmpty()) {
			int[] loc = q.poll();
			
			for(int d = 0; d < 4; d++) {
				int nr = loc[0] + dr[d];
				int nc = loc[1] + dc[d];
				if(nr < 0 || nr >= N || nc < 0 || nc >= M || v[nr][nc] || map[nr][nc] == 1) continue;
				if(map[nr][nc] == 3 || map[nr][nc] == 4 || map[nr][nc] == 5) return loc[2]+1;
				v[nr][nc] = true;
				q.offer(new int[] {nr, nc, loc[2]+1});
			}
		}
		return -1;
	}
}