글 읽기 - Java 예제는 잘 동작하는데, 반례 좀 찾아주실 수 있을까요?

sekhyun92 3년 전 0

예제를 포함한 게시판 내 웬만한 반례들은 다 잘 동작하는거 같은데 자꾸 틀렸다고 나오네요ㅠㅠ

고수님들 반례 부탁드리겠습니다!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	static Queue<Node> queue = new LinkedList<Node>();
	static ArrayList<Node> nodes = new ArrayList<Node>();

	static class Node {
		int data;
		boolean visited;

		Node(int data) {
			this.data = data;
		}
	}

	static ArrayList<Node> findNeighbours(int matrix[][], Node x) {
		int nodeIndex = -1;
		ArrayList<Node> neighbours = new ArrayList<Node>();

		for (int i = 0; i < nodes.size(); i++) {
			if (nodes.get(i).equals(x)) {
				nodeIndex = i;
				break;
			}
		}

		if (nodeIndex != -1) {
			for (int j = 0; j < matrix[nodeIndex].length; j++) {
				if (matrix[nodeIndex][j] == 1) {
					neighbours.add(nodes.get(j));
				}
			}
		}

		return neighbours;
	}

	static void bfs(int matrix[][], Node node) {
		queue.add(node);
		node.visited = true;

		while (!queue.isEmpty()) {
			Node element = queue.remove();
			ArrayList<Node> neighbours = findNeighbours(matrix, element);
			for (int i = 0; i < neighbours.size(); i++) {
				Node n = neighbours.get(i);
				if (n != null && !n.visited) {
					queue.add(n);
					n.visited = true;
				}
			}
		}
	}

	public static void main(String arg[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		int count[] = new int[T];

		for (int i = 0; i < T; i++) {
			String inputArr[] = br.readLine().split(" ");
			int M = Integer.parseInt(inputArr[0]);
			int N = Integer.parseInt(inputArr[1]);
			int K = Integer.parseInt(inputArr[2]);

			for (int j = 0; j < N * M; j++) {
				nodes.add(new Node(j));
			}

			int P[][] = new int[N][];
			for (int j = 0; j < N; j++) {
				P[j] = new int[M];
			}

			for (int k = 0; k < K; k++) {
				String pArr[] = br.readLine().split(" ");
				P[Integer.parseInt(pArr[1])][Integer.parseInt(pArr[0])] = 1;
			}

			int matrix[][] = new int[N * M][];
			for (int j = 0; j < N * M; j++) {
				matrix[j] = new int[N * M];
			}

			boolean isAlone = true;
			for (int j = 0; j < N; j++) {
				for (int k = 0; k < M; k++) {
					if (P[j][k] == 1) {
						if (j - 1 > -1)
							if (P[j - 1][k] == 1) {
								matrix[j * M + k][(j - 1) * M + k] = 1;
								matrix[(j - 1) * M + k][j * M + k] = 1;
								isAlone = false;
							}
						if (j + 1 < N)
							if (P[j + 1][k] == 1) {
								matrix[j * M + k][(j + 1) * M + k] = 1;
								matrix[(j + 1) * M + k][j * M + k] = 1;
								isAlone = false;
							}
						if (k - 1 > -1)
							if (P[j][k - 1] == 1) {
								matrix[j * M + k][j * M + (k - 1)] = 1;
								matrix[j * M + (k - 1)][j * M + k] = 1;
								isAlone = false;
							}
						if (k + 1 < M)
							if (P[j][k + 1] == 1) {
								matrix[j * M + k][j * M + (k + 1)] = 1;
								matrix[j * M + (k + 1)][j * M + k] = 1;
								isAlone = false;
							}

						if (isAlone) {
							count[i]++;
						}

						isAlone = true;
					}
				}
			}

			for (int j = 0; j < N * M; j++) {
				if (!nodes.get(j).visited && findNeighbours(matrix, nodes.get(j)).size() != 0) {
					bfs(matrix, nodes.get(j));
					count[i]++;
				}
			}
		}

		for (int i = 0; i < T; i++) {
			System.out.println(count[i]);
		}
	}
}

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

문제

문제

출처

ICPC

Java 예제는 잘 동작하는데, 반례 좀 찾아주실 수 있을까요?

sekhyun92 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말