글 읽기 - bfs 로 풀었고 4퍼센트에서 자꾸 틀렸습니다가 뜨네요.

pose2done 6년 전 0

질문에 올라온 예외 케이스들 도 다 맞긴한데 어딘가 분명히 틀렸을텐데...

도와주실 수 있는분이나 혹여 예외케이스 찾아주신다면 정말 감사하겠습니다.

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

public class Main {
	
	private static char[][] map;
	private static int[] di = {0,1,0,-1};
	private static int[] dj = {1,0,-1,0};
	private static boolean[][][][] visit;
	
	
	private static Queue<Balls> ballsQ ;
	
	public static void main(String args[])throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		map = new char[n][m];
		
		ArrayList<Ball> twoBalls = new ArrayList<>();
		
		
		int rx=0;
		int ry=0;
		int bx=0;
		int by=0;
		
		
		
		for(int i = 0; i<n ; i++){
			String tmp = br.readLine();
			for(int j = 0; j<m; j++){
				map[i][j] = tmp.charAt(j);
				if(map[i][j] == 'R'){
					rx = i;
					ry = j;
					twoBalls.add(new Ball(map[i][j],i,j,false));
					map[i][j] = '.';
				}
				if( map[i][j] =='B'){
					bx = i;
					by = j;
					twoBalls.add(new Ball(map[i][j],i,j,false));
					map[i][j] = '.';
				}
			}
		}
		
		Balls starter = new Balls(0, twoBalls);
		
		
		visit = new boolean[10][10][10][10];
		visit[rx][ry][bx][by] = true;
		ballsQ = new LinkedList<>();
		ballsQ.offer(starter);
		
		
		while(!ballsQ.isEmpty()){
			
			Balls tmpBalls = ballsQ.poll();
			
			if(tmpBalls.count >10){
				System.out.println(-1);
				return;
			}
			
			for(int i =0;i<4; i++){
				if(move(tmpBalls,i)){
					System.out.println(tmpBalls.count+1);
					return;
				}
			}
			
		}
		System.out.println(-1);
		
	}
	static class Ball{
		char color;
		int x;
		int y;
		boolean status; //빠짐 안빠짐.
		public Ball(char color, int x, int y, boolean status) {
			super();
			this.color = color;
			this.x = x;
			this.y = y;
			this.status = status;
		}
	}
	static class Balls{
		int count;
		ArrayList<Ball> twoBalls;
		public Balls(int count, ArrayList<Ball> twoBalls) {
			super();
			this.count = count;
			this.twoBalls = twoBalls;
		}
	}
	public static boolean move(Balls tmpBalls, int direction){
		
		Comp comparator = new Comp(direction);
		ArrayList<Ball> tmpTwoBalls = (ArrayList<Ball>) tmpBalls.twoBalls.clone();
		
		Collections.sort(tmpTwoBalls,comparator);
		
		Ball firstBall = new Ball(tmpTwoBalls.get(0).color,tmpTwoBalls.get(0).x,tmpTwoBalls.get(0).y,tmpTwoBalls.get(0).status);
		Ball secondBall = new Ball(tmpTwoBalls.get(1).color,tmpTwoBalls.get(1).x,tmpTwoBalls.get(1).y,tmpTwoBalls.get(1).status);
		
		//순서가 정해졌으므로 어레이리스트의 앞에것부터 process한다.
		
		int firstBallX = firstBall.x;
		int firstBallY = firstBall.y;
		
		int secondBallX = secondBall.x;
		int secondBallY = secondBall.y;
		
		//첫번째공을 방향으로 밀어넣으면서 벽을만나거나 구멍에 빠지거나하는 상황을 확인한다.
		Loop1 : while(true){
			firstBallX += di[direction];
			firstBallY += dj[direction];
            
			switch(map[firstBallX][firstBallY]){	
			case 'O' : 
				firstBall.x = firstBallX;
				firstBall.y = firstBallY;
				firstBall.status = true;
				break Loop1;
			case '.' : 
				continue Loop1;
			case '#' :
				firstBall.x = firstBallX - di[direction];
				firstBall.y = firstBallY - dj[direction];
				map[firstBall.x][firstBall.y] = '#'; // 나중에 다시 지워줘야함.
				break Loop1;
				default : System.out.println("안걸림 move switch"); break;
			}
		}
		
		Loop2 : while(true){
	
			secondBallX += di[direction];
			secondBallY += dj[direction];
			
			switch(map[secondBallX][secondBallY]){
			case 'O' : 
				secondBall.x = secondBallX;
				secondBall.y = secondBallY;
				secondBall.status = true;
				break Loop2;
			case '.' : 
				continue Loop2;
			case '#' :
				secondBall.x = secondBallX - di[direction];
				secondBall.y = secondBallY - dj[direction];
				break Loop2;
				default : System.out.println("안걸림 move switch"); break;
			}
			
		}
		
		map[firstBall.x][firstBall.y] = '.';
		
		Ball redBall = new Ball('X', 0, 0, true);
		Ball blueBall = new Ball('X', 0, 0, true);
		
		if(firstBall.color == 'R') redBall = firstBall;
		if(firstBall.color == 'B') blueBall = firstBall;
		if(secondBall.color == 'R') redBall = secondBall;
		if(secondBall.color == 'B') blueBall = secondBall;
		
//		System.out.println("redBall : " + redBall.x + " , " + redBall.y + " blueBall : " + blueBall.x + " , " + blueBall.y);
		
		//한번 왔던 redBall 과 blueBall의 그자리 그대로 왔으면 최적의 답이 아니므로 pass시키기위함
		if(visit[redBall.x][redBall.y][blueBall.x][blueBall.y])return false;
		visit[redBall.x][redBall.y][blueBall.x][blueBall.y] = true;
		
		if(blueBall.status)return false;
		if(redBall.status)return true;
		
		ArrayList<Ball> tmpTwoBalls2 = new ArrayList<>();
		tmpTwoBalls2.add(firstBall);
		tmpTwoBalls2.add(secondBall);
		
		ballsQ.offer(new Balls(tmpBalls.count+1,tmpTwoBalls2));
		return false;
	}
	//벽부터 가까운놈을 먼저 실행시키기위한 Comp
	static class Comp implements Comparator<Ball>{
		int direction;

		public Comp(int direction) {
			super();
			this.direction = direction;
		}

		@Override
		public int compare(Ball o1, Ball o2) {
			// TODO Auto-generated method stub
			switch(direction){
			case 0:
				
				return o2.y - o1.y;
			
			case 1:
				
				return o2.x - o1.x;
			
			case 2:

				return o1.y-o2.y;
			
			case 3:
				
				return o1.x - o2.x;
				
			default : System.out.println("안걸림"); break;
			}
			
			return 0;
		}
		
	}
}

pose2done 6년 전 0

아 이거 틀린거 찾았네요,,, 제가 먼저 온 공 예외처리해줄때

구멍에 빠졌더라도 막힌 공처럼 처리를 전역변수의 맵에다가 해버려서 그런거였습니다... ㅠㅠ

145번째줄이랑 173번째 줄.. 저거 둘다 if 문으로 map그 부분이 O가 아닐때만 실행해야할 문장이었어요

sorrly 6년 전 0

저도 그런 에러 해결했는데요...ㅠ

그래도 4%을 못넘네요.ㅠㅠ

님은 해결 잘 되셨나요?

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

문제

문제

출처

ICPC

bfs 로 풀었고 4퍼센트에서 자꾸 틀렸습니다가 뜨네요.

pose2done 6년 전 0

pose2done 6년 전 0

sorrly 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말