글 읽기 - 구슬탈출2 , 게시판 테스트케이스는 모두 통과하는데 반례를 알 수 있을까요?

imsosleepy 5년 전 0

타임아웃은 간신히 견뎌내는거 같은데

60%에서 틀렸습니다가 나오네요.

반례를 알 수 있을까요?

반례가 아니면 분명히 사소한 문제에 걸린 것 같은데 답변 부탁드립니다.

import java.awt.Point;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	int N;
	int M;
	String[][] map;
	boolean[] visited;
	
	int count = Integer.MAX_VALUE;
	
	int min = Integer.MAX_VALUE;
	
	Ball blueBall;
	Ball redBall;
	
	public Main() {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		
		map = new String[N][M];
		visited = new boolean[4];
		// red: 0 , blue : 1
		for(int i=0;i<N;i++) {
			String s =sc.next();
			String[] temp = s.split("");
			for(int j=0;j<M;j++) {
				map[i][j] = temp[j];
				if(map[i][j].equals("R")) redBall = new Ball(i,j,0);
				if(map[i][j].equals("B")) blueBall = new Ball(i,j,1);
			}
		}
		
		DFS(0,0);
		// answer가 초기화 상태면 한번도 O에 골을 못했다는 뜻
		if(answer == Integer.MAX_VALUE) System.out.println(-1);
		else System.out.println(answer+1); // ans에 0부터 시작하는 cnt로 체크했기때문에 +1
	}
	
	int answer = Integer.MAX_VALUE;
	boolean blueOut = false;
	public void DFS(int direct, int cnt) {
		if(cnt == 10) {
			return;
		}
		// 0-3까지가 기울이는 방향
		for(int i=0;i<4;i++) {
			// 0->0->0은 아무의미없어서 반복안되게
			if(visited[i]) continue;
			visited = new boolean[4];
			visited[i] = true;
			// 이전상황 맵, 공위치 복사
			String [][] copyMap = new String[N][M];
			copyMap = mapCopy(map,copyMap);
			Ball tempRedBall = new Ball(redBall.x,redBall.y,0);
			Ball tempBlueBall = new Ball(blueBall.x,blueBall.y,1);
			
			// 공을 이동시켰을때 빨간공이 들어갔는지 테스트
			if(moveBall(i, redBall, blueBall, cnt)) {
				answer = Math.min(answer,cnt);
			}
			// 파란공이 O에 들어갔을때, 이 방향으론 지속해도 의미가 없다. continue;
			// 공이랑 맵상황 실행 전 위치로
			if(blueOut) {
				blueOut=false;
				map = mapCopy(copyMap,map);
				redBall = new Ball(tempRedBall.x,tempRedBall.y,0);
				blueBall = new Ball(tempBlueBall.x,tempBlueBall.y,1);
				continue;
			}
			// 다음 방향으로 이동
			DFS(i,cnt+1);
			// back trace
			// 이전상황 맵, 공위치 가져오기
			visited[i] = false;
			map = mapCopy(copyMap,map);
			redBall = new Ball(tempRedBall.x,tempRedBall.y,0);
			blueBall = new Ball(tempBlueBall.x,tempBlueBall.y,1);
		}
	}
	
	// 맵복사 매서드
	public String[][] mapCopy(String[][] map, String[][] copyMap){
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				copyMap[i][j] = map[i][j];
			}
		}
		
		return copyMap;
	}
	
	// 위로
	public boolean moveUp(Ball ball) {
		boolean isGoal = false;
		for(int i=1;i<N;i++) {
			int nx = ball.x-i;
			int ny = ball.y;
			if(map[nx][ny].equals("O")) {
				if(ball.type == 1) blueOut = true;
				isGoal = true;
				break;
			}
			if(map[nx][ny].equals("#") || map[nx][ny].equals("B")|| map[nx][ny].equals("R")) {
				if(ball.type == 0) {
					map[nx+1][ny] = "R";
					redBall = new Ball(nx+1,ny,0);
				}
				if(ball.type == 1) {
					map[nx+1][ny] = "B";
					blueBall = new Ball(nx+1,ny,1);
				}
				break;
			}
		}
		return isGoal;
	}
	// 오른쪽으로
	public boolean moveRight(Ball ball) {
		boolean isGoal = false;
		for(int i=1;i<M;i++) {
			int nx = ball.x;
			int ny = ball.y+i;
			if(map[nx][ny].equals("O")) {
				if(ball.type == 1) blueOut = true;
				isGoal = true;
				break;
			}
			if(map[nx][ny].equals("#") || map[nx][ny].equals("B") || map[nx][ny].equals("R")) {
				if(ball.type == 0) {
					map[nx][ny-1] = "R";
					redBall = new Ball(nx,ny-1,0);
				}
				if(ball.type == 1) {
					map[nx][ny-1] = "B";
					blueBall = new Ball(nx,ny-1,1);
				}
				break;
			}
		}
		return isGoal;
	}
	// 아래로
	public boolean moveDown(Ball ball) {
		boolean isGoal = false;
		for(int i=1;i<N;i++) {
			int nx = ball.x+i;
			int ny = ball.y;
			if(map[nx][ny].equals("O")) {
				if(ball.type == 1) blueOut = true;
				isGoal = true;
				break;
			}
			if(map[nx][ny].equals("#") || map[nx][ny].equals("B") || map[nx][ny].equals("R")) {
				if(ball.type == 0) {
					map[nx-1][ny] = "R";
					redBall = new Ball(nx-1,ny,0);
				}
				if(ball.type == 1) {
					map[nx-1][ny] = "B";
					blueBall = new Ball(nx-1,ny,1);
				}
				break;
			}
		}
		return isGoal;
	}
	// 왼쪽으로
	public boolean moveLeft(Ball ball) {
		boolean isGoal = false;
		for(int i=1;i<M;i++) {
			int nx = ball.x;
			int ny = ball.y-i;
			if(map[nx][ny].equals("O")) {
				if(ball.type == 1) blueOut = true;
				isGoal = true;
				break;
			}
			if(map[nx][ny].equals("#") || map[nx][ny].equals("B") || map[nx][ny].equals("R")) {
				if(ball.type == 0) {
					map[nx][ny+1] = "R";
					redBall = new Ball(nx,ny+1,0);
				}
				if(ball.type == 1) {
					map[nx][ny+1] = "B";
					blueBall = new Ball(nx,ny+1,1);
				}
				break;
			}
		}
		return isGoal;
	}
	
	// 이동 알고리즘
	public boolean moveBall(int direct, Ball red, Ball blue,int moveCount) {
		map[red.x][red.y] = "."; // 원래 있던 장소를 공백으로 만들기
		map[blue.x][blue.y] = ".";
		boolean blueGoal = false;
		boolean redGoal = false;
		switch (direct) {
		case 0: // 북쪽		
			if(red.x<blue.x) { // 빨간공이 파란공 위에 있을때
				redGoal = moveUp(red);
				blueGoal = moveUp(blue);
			}else { // 빨간공이 파란공 아래 있을 때
				blueGoal = moveUp(blue);
				redGoal = moveUp(red);
			}
			break;
		case 1: // 동쪽
			if(red.y>blue.y) { // 빨간공이 파란공 오른쪽 있을때
				redGoal = moveRight(red);
				blueGoal =moveRight(blue);
			}else { 
				blueGoal =moveRight(blue);
				redGoal = moveRight(red);
			}
			break;
		case 2: // 남쪽
			if(red.x>blue.x) { // 빨간공이 파란공 아래에 있을때
				redGoal = moveDown(red);
				blueGoal =moveDown(blue);
			}else {
				blueGoal =moveDown(blue);
				redGoal = moveDown(red);
			}
			break;
		case 3: // 서쪽
			if(red.y<blue.y) { // 빨간공이 파란공 왼쪽 있을때
				redGoal = moveLeft(red);
				blueGoal = moveLeft(blue);
			}else { 
				blueGoal = moveLeft(blue);
				redGoal = moveLeft(red);
			}
			break;
		}
		// 둘다 골에 들어왔을때는 안되는 경우
		if(blueGoal && redGoal) return false;
		// 블루만 골에 들어왔을때도 안되는 경우
		else if(blueGoal && redGoal == false) return false;
		// 레드만 골에 들어와야한다.
		else if(redGoal && blueGoal == false) return true;
		// 둘다 골에 안들어왔을 때,
		else return false;
	}
	// 공 클래스
	public class Ball{
		int x;
		int y;
		int type; // red: 0 , blue :1
		public Ball(int x, int y, int type) {
			this.x = x;
			this.y = y;
			this.type = type;
		}
	}
	

	public static void main(String[] args) {
		new Main();
	}
}

djm03178 5년 전 2

랜덤 반례 드립니다.

7 6
######
######
####.#
#.R#.#
#.#.##
#O.B.#
######
output: -1
correct answer: 3

6 7
#######
##.##.#
#.B.#.#
#O..R##
#.#...#
#######
output: 2
correct answer: 1

4 6
######
#..###
#OBR##
######
output: 10
correct answer: 2

imsosleepy 5년 전 0

답변감사드립니다.

반복진입을 막기 위한 visited 행렬에 문제가 있었네요.

왜 문제가 있었는지는 생각을 해봐야겠습니다.

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

문제

문제

출처

ICPC

구슬탈출2 , 게시판 테스트케이스는 모두 통과하는데 반례를 알 수 있을까요?

imsosleepy 5년 전 0

djm03178 5년 전 2

imsosleepy 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말