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

문제링크

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

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int n, m;
	static int map[][];
	static boolean isVisited[][];
	static boolean isFind;
	static int result = Integer.MAX_VALUE;
	static Queue<Node> q = new LinkedList<>();
	static int dx[] = {0,0,-1,1};
	static int dy[] = {-1,1,0,0};

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		map = new int[n][m];
		isVisited = new boolean[n][m];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			String str = st.nextToken();
			for (int j = 0; j < m; j++) {
				map[i][j] = str.charAt(j) - '0';
				if (map[i][j] == 2)
					q.offer(new Node(i,j,0));
			}
		}

		bfs();
		if(isFind) {
			System.out.println("TAK");
			System.out.println(result);
		}
		else
			System.out.println("NIE");
	}

	static void bfs() {
		
		while(!q.isEmpty()) {
			Node node = q.poll();
			
			for(int d=0;d<4;d++) {
				int nx = node.x + dx[d];
				int ny = node.y + dy[d];
				
				if(nx<0 || nx>=n || ny<0 || ny>=m || isVisited[nx][ny] || map[nx][ny]==1) continue;
				
				if(map[nx][ny] ==3 || map[nx][ny] ==4 || map[nx][ny] ==5) {
					//음식 찾음
					isFind = true;
					result = node.weight+1;
					return;
					
				}
				
				isVisited[nx][ny] = true;
				q.offer(new Node(nx,ny,node.weight+1));
			}
		}
	}
	
	static class Node{
		int x;
		int y;
		int weight;
		public Node(int x, int y, int weight) {
			super();
			this.x = x;
			this.y = y;
			this.weight = weight;
		}
	}
}

좌표와 길이를 저장해줄 클래스이다.

 

BFS함수이다.

만약 배열의 범위를 벗어나거나 방문했던 좌표거나 1이어서 지나갈 수 없는 길이면 CONTINUE를 통해 지나쳐준다.

혹시  map[nx][ny]가 3,4,5이면 음식이므로 음식을 찾았다는 표시를 해주기 위해 isFind를 true로 바꾸어주고 길이는 node.weight+1로 설정하여준다. 

weight는 현재 길이를 담고있는 변수로 현재 큐에 담겨있었던 좌표까지의 거리가 weight이므로

한칸 더 앞으로 나아갈 nx,ny가 음식에 도착하였으므로 +1을 해주어야한다.

그리고 bfs의 특성상 제일먼저 발견되었으면 가장 최단거리가 됨으로 return을 해주어도된다.