글 읽기 - 60%대에서 틀립니다.. 반례를 알고 싶습니다. JAVA

qkfskan82 2년 전 0

문제예제와 질문게시판의 반례는 전부 테스트해본것 같은데 문제없이 통과합니다.

정확히 보진 못했지만 테스트케이스 65% 진행도에서 오답처리되는데 반례가 알고 싶습니다...

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

public class Main{
	static StringTokenizer st;
	static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		char[][] map = new char[N][M];
		boolean[][][][] visited = new boolean[N][M][N][M];
		int redX = 0, redY = 0, blueX = 0, blueY = 0;

		Queue<int[]> queue = new LinkedList<>();

		for (int n = 0; n < N; n++) {
			char[] input = br.readLine().toCharArray();
			for (int m = 0; m < M; m++) {
				map[n][m] = input[m];
				if (input[m] == 'R') {
					redX = n;
					redY = m;
					map[n][m] = '.';
				}
				if (input[m] == 'B') {
					blueX = n;
					blueY = m;
					map[n][m] = '.';
				}
			}
		}

		queue.offer(new int[] { redX, redY, blueX, blueY });
		visited[redX][redY][blueX][blueY] = true;

		int time = 0;
		int answer = 0;

		loop: while (!queue.isEmpty()) {
			int size = queue.size();

			while (size-- > 0) {
				int[] now = queue.poll();

				for (int i = 0; i < 4; i++) {
					int nrX = now[0], nrY = now[1], nbX = now[2], nbY = now[3];
					int moveR = 0, moveB = 0;
					boolean blueFlag = false;
					while (true) {
						nbX += delta[i][0];
						nbY += delta[i][1];
						if (map[nbX][nbY] == '#') {
							nbX -= delta[i][0];
							nbY -= delta[i][1];
							break;
                            //벽을 만나면 온 방향으로 한칸을 다시 돌려주고 루프를 아웃
						} else if (map[nbX][nbY] == 'O') {
							blueFlag = true;
							break;
						} else {
							moveB++;
						}
					}
                    // 파란공을 먼저 처리하는 이유는 빨간공이 성공해도 파란공이 같은 턴에 들어가면 실패이기 때문입니다.
                    // 빨간공이 들어가고 파란공이 들어가는 경우에는 빨간공을 무시하고 파란공을 진행해도 똑같은 결과가 나오고
                    // 파란공이 먼저 들어가는 경우에는 당연히 파란공을 먼저 진행해도 들어갑니다.
                    
                    //피린공이 들어간 경우에는 빨간공을 탐색하는 의미가 없으므로 스킵합니다.
					while (!blueFlag) {
						nrX += delta[i][0];
						nrY += delta[i][1];
						if (map[nrX][nrY] == '#') {
							nrX -= delta[i][0];
							nrY -= delta[i][1];
							break;
						} else if (map[nrX][nrY] == 'O') {
							answer = 1;
							break loop;
						} else {
							moveR++;
						}
					}

                    //파란공이 들어가지 않은 경우, 즉 더 탐색해볼 가치가 있는 경우
					if (!blueFlag) {
						if (nrX == nbX && nrY == nbY) {
							if (moveR > moveB) {
								nrX -= delta[i][0];
								nrY -= delta[i][1];
							} else {
								nbX -= delta[i][0];
								nbY -= delta[i][1];
							}
                            //공의 충돌여부를 판단해서 더 많이 움직인 공, 즉 늦게 도착한 공을 한 칸 뒤로
						}

                        //탐색하지 않은 상황이면 큐에 넣고 방문처리
						if (!visited[nrX][nrY][nbX][nbY]) {
							visited[nrX][nrY][nbX][nbY] = true;
							queue.offer(new int[] { nrX, nrY, nbX, nbY });
						}
					}
				}
			}
            //시간이 10이 넘은 경우 루프문 아웃
			if (time++ == 10) {
				break;
			}
		}

		System.out.println(answer);
	}
}

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

문제

문제

출처

ICPC

60%대에서 틀립니다.. 반례를 알고 싶습니다. JAVA

qkfskan82 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말