[백준 17086] 실버1 -아기 상어 2

www.acmicpc.net/problem/17086

17086번: 아기 상어 2

풀이시간: 50분

 

1. 개념

BFS

 

2. 풀이

큐에 x, y, d를 넣고나서 bfs를 돌린다

 

3. 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class back_아기상어217086 {
	static int n, m, map[][];
	static int dr[] = { -1, -1, -1, 0, 1, 1, 1, 0 };
	static int dc[] = { -1, 0, 1, 1, 1, 0, -1, -1 };

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		map = new int[n][m];
		int answer = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		int temp = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] == 1)
					continue;
				temp = go(i, j);
				answer = temp > answer ? temp : answer;
			}
		}
		System.out.println(answer);
	}

	static int go(int r, int c) {
		boolean visit[][] = new boolean[n][m];
		Queue<int[]> q = new LinkedList<>();
		q.add(new int[] { r, c, 0 });
		visit[r][c] = true;
		int cnt = 0;
		while (!q.isEmpty()) {
			int cur[] = q.poll();
			for (int i = 0; i < 8; i++) {
				int ny = cur[0] + dr[i];
				int nx = cur[1] + dc[i];
				int d = cur[2];
				if (ny < 0 || nx < 0 || ny >= n || nx >= m)
					continue;
				if (visit[ny][nx]==true)
					continue;
				if (map[ny][nx] == 1) {
					return d+1;
				}
				visit[ny][nx] = true;
				q.add(new int[] {ny,nx, d+1});
			}
		}
		return 0;
	}
}

 

큐에 배열 넣기

q.add(new int[] { r, c, 0 });

 

1을 만나면 지금까지 이동한 거리를 return

if (map[ny][nx] == 1) {
	return d+1;
}