글 읽기 - 여러 반례를 대입해보았으나 도대체 어디가 틀렸는지 모르겠습니다

hj97718 3년 전 0

그림을 한칸씩 방문하면서 방문하지 않은 색깔이면 너비 우선 탐색을 합니다.

탐색을 하면서 방문한 좌표를 탐색하였을 때 R이나 G리면 한 공간으로 인식하도록 boolean-true 값을 리턴하여

해당 값이 true면 색약이 판단하는 공간의 값을 1개 줄여주었습니다.

질문 검색에서 찾은 반례들도 다 맞게 잘 나오고 테스트 케이스도 잘 나오는데 채점해보면 틀렸다고 나옵니다.

도대체 어느 부분에서 틀렸는지 모르겠습니다.

반례가 있으면 알려주시기 바랍니다..

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	static int N;
	static char[][] picture;
	static int normal = 0, weak = 0;
	static int[] dx = { 0, 0, 1, -1 }, dy = { 1, -1, 0, 0 };

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());

        // 그림
		picture = new char[N][N];
        // 방문 여부를 확인하는 배열
		boolean[][] visited = new boolean[N][N];

		for (int i = 0; i < N; i++) {
			picture[i] = br.readLine().toCharArray();
		}

		for (int x = 0; x < N; x++) {
			for (int y = 0; y < N; y++) {
                // 방문하지 않은 공간이면
				if (!visited[x][y]) {
                    // 정상인이 보는 색깔 범위 증가
					normal += 1;
                    // 색약이 보는 색깔 범위 증가
					weak += 1;

					boolean isColorWeak = solution(picture[x][y], x, y, visited);

                    // 같은 색깔로 보는 공간이 있으면
					if (isColorWeak) {
                        // 색약이 보는 색깔 범위 감소
						weak -= 1;
					}
				}
			}
		}

		System.out.println(normal + " " + weak);

	}

	public static boolean solution(char color, int x, int y, boolean[][] visited) {
		Queue<Point> queue = new LinkedList<Point>();
		boolean isColorWeak = false;

		queue.add(new Point(x, y));
		visited[x][y] = true;

		while (!queue.isEmpty()) {
			Point current = queue.poll();

			for (int i = 0; i < 4; i++) {
				int newX = current.x + dx[i];
				int newY = current.y + dy[i];

				// 새로운 좌표가 범위 안이면
				if (isIn(newX, newY)) {
					// 주위의 방문한 죄표 중에 색약에 해당되는 색깔이 있으면
					if (visited[newX][newY]) {
						if ((color == 'R' && picture[newX][newY] == 'G')
								|| (color == 'G' && picture[newX][newY] == 'R')) {
							isColorWeak = true;
						}
					}

					// 방문하지 않았고, 다음에 방문할 색깔이 기준 색깔과 같을 때
					if (!visited[newX][newY] && picture[newX][newY] == color) {
						queue.add(new Point(newX, newY));
						visited[newX][newY] = true;
					}
				}
			}
		}

		return isColorWeak;
	}

	public static boolean isIn(int x, int y) {
		if (0 <= x && x < N && 0 <= y && y < N) {
			return true;
		}
		return false;
	}

}

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

문제

문제

출처

ICPC

여러 반례를 대입해보았으나 도대체 어디가 틀렸는지 모르겠습니다

hj97718 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말