글 읽기 - bfs 탐색이 되지 않고 매번 cnt가 호출됩니다.

ejc0628 3년 전 0

bfs로 접근하여 푸는 문제인 것 같아,

bfs함수를 정의하고 if문으로 조건을 걸어주었습니다. 조건을 만족하지 않는 경우 continue;를 추가하였습니다.

하지만, 결과는 cnt가 1이 나올때마다 더해지는 형태로 나옵니다.. 이유가 있을까요?

package BFS;


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

public class Q4963 {

	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	public static StringTokenizer st;
	public static int array[][];
	public static boolean check[][]; // 방문 여부를 확인
	public static final int dx[] = { -1, -1, -1, 0, 1, 1, 1, 0 };
	public static final int dy[] = { -1, 0, 1, 1, 1, 0, -1, -1 };

	public static void main(String[] args) throws IOException {

		int n;
		int m;
		while (true) {
			st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken()); // 3
			m = Integer.parseInt(st.nextToken()); // 2

			if (n == 0 && m == 0)
				break; // 종료 조건
			makeArray(n, m);
		}

		bw.flush();
		bw.close();
	}

	private static void makeArray(int n, int m) throws IOException {
		int cnt = 0;
		array = new int[m + 1][n + 1];
		check = new boolean[m + 1][n + 1];
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++) {
				array[i][j] = Integer.parseInt(st.nextToken());
				if (array[i][j] == 1 && !check[i][j]) {
					bfs(i, j, m, n);
					cnt++;
				}
			}
		}
		bw.write(cnt + "\n");

	}

	private static void bfs(int m, int n, int i, int j) {

		Queue<Point> q = new LinkedList<Point>();
		int nx, ny;
		q.offer(new Point(i, j));

		while (!q.isEmpty()) {
			Point temp = q.poll();
			for (int a = 0; a < 8; a++) {
				nx = temp.x + dx[a];
				ny = temp.y + dy[a];

				if (nx < 0 || ny < 0 || nx >= m || ny >= n)
					continue;
				if (array[nx][ny] == 0 || check[nx][ny])
					continue;

				check[nx][ny] = true;
				q.offer(new Point(nx, ny));
			}
		}

	}
    static class Point {
		
		int x;
		int y;
		
		Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

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

문제

문제

출처

ICPC

bfs 탐색이 되지 않고 매번 cnt가 호출됩니다.

ejc0628 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말