글 읽기 - bfs 방법에서 틀린부분 좀 찾아주세요

hds1630 6년 전 0

dfs로 해결은 했는데 bfs로는 틀리다고 나오네요.. 어느부분에서 틀렸는지 고수님들 알려주세요

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

public class bj2468 {
	static int arr[][];
	static boolean visited[][];

	static int dx[] = { -1, 0, 1, 0 };
	static int dy[] = { 0, -1, 0, 1 };

	static int n, cnt;
	static int max = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();

		arr = new int[n][n];
		visited = new boolean[n][n];

		int big = 0;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				arr[i][j] = sc.nextInt();
				if (arr[i][j] > big)
					big = arr[i][j];
			}
		}

		for (int k = 1; k <= 100; k++) {

			cnt = 0;

			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (arr[i][j] > k && !visited[i][j]) {
						bfs(k, j, i);
					}
				}
			}
			System.out.println(cnt);
			if (cnt > max) {
				max = cnt;
			}
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					visited[i][j] = false;
				}
			}

		}
		System.out.println(max);
	}

	public static void bfs(int k, int x, int y) {
		Queue<Pair> q = new LinkedList<>();
		q.add(new Pair(x, y));
		cnt++;

		while (!q.isEmpty()) {
			Pair p = q.poll();

			for (int i = 0; i < 4; i++) {
				int nx = p.x + dx[i];
				int ny = p.y + dy[i];

				if (nx < 0 || ny < 0 || nx >= n || ny >= n)
					continue;

				if (arr[ny][nx] > k && !visited[ny][nx]) {
					visited[ny][nx] = true;
					q.add(new Pair(nx, ny));
				}

			}
		}

	}

	public static class Pair {
		int x;
		int y;

		Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

bfs 방법에서 틀린부분 좀 찾아주세요

hds1630 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말