글 읽기 - 혹시 정답 체점 여러경우의수 가능한데 제꺼 맞는지 확인부탁드려요..

teahyuk 8년 전 0

예제보니깐 여러경우의수가 가능하드라구요.

우선 예제만 봐도 RUR도 됩니다.

혹시나해서 남겨요~.

일단 저는 다소 복잡하게 짯는데요..

그냥 모든 통로에 쌀알이 있다고 생각하고 다 빼는 방식으로 했습니다.

속도 생각해서 코드가쪼금 길게 나오네요...

BFS방식이라 한거는 다음번 기울인 상태를 큐에 저장해놨다가 직전 상태에서 움직일수있는 모든 경우의수를 끝낸뒤에 넘어간다고 해서 BFS 방식이라했구요.

뭐 큐에 저장만 했지 따로 그래프 구조 만든건 아닙니다. 미로찾기할때 BFS한것과 비슷해요.

우선 첫번째 상태를 모든 '.' 에 쌀알(balls)가 있다 라고 정합니다.

그다음 어떤 방향으로든 움직일 때마다 벽으로 다 쏠린다고 생각하고 없애고 합칩니다.

이 과정들은 전 자바로 했기때문에 Set 이용해서, HashSet에다가, 쌀알이 있는 좌표 들만 넣었구요.

하단에 상태 class(Balls) 안에 내부class(balls)가 있고 쌀알을 표현하는 내부클래스 (balls)는 x,y좌표밖에 없고 이거를 상태class(Balls)가 Set으로 가지고있어요. 그리고 상태클래스는 set의 길이를 length로가지고, 현재까지 움직인 경로를 trace로 가지고있습니다.

주요 메소드 및 알고리즘은 메인에 //bfs방식부분이구요.

하단 상태class(Balls)에 move메소드가 되겠네요.

나머지는 contains나 Set.add할때 편하게 하려고 eqauls같은거 전부 오버라이드해논거구요. 생성자랑..

제 방식이 잘못된게 있는것일까요;;...ㅠㅠ

알려주세요~!.ㅠㅠ

import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;



public class Main{
	static char[][] Maze;
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        
        int T=sc.nextInt();
        Case : for (int i = 0; i < T; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
	        Maze = new char[x][y];
	        sc.nextLine();
	        for (int j = 0; j < Maze.length; j++) {
				String tmp = sc.nextLine();
	        	for (int k = 0; k < Maze[j].length; k++) {
	        		Maze[j][k] = tmp.charAt(k);
				}
			}
	        //bfs방식.
	        Balls answer = new Balls(Maze);
	        Queue<Balls> Q = new LinkedList<>();
	        Stack<Balls> visited = new Stack<>();
	        Q.offer(answer);
	     
	        while(!Q.isEmpty()){
	        	Balls tmp = Q.poll();
	        	//이전상태와 같나 확인.
	        	if(visited.contains(tmp))
	        		continue;
	        	//안같으면 visited 저장.
	        	visited.push(tmp);
	        	
	        	//성공여부.
	        	if(tmp.length==0){
	        		System.out.println(tmp.trace);
	        		continue Case;
	        	}
	        	else if(tmp.trace.length()>10)
	        		continue;
	        	
	        	//다음 스텝 움직이기.
	        	Q.offer(tmp.move('U', Maze));
	        	Q.offer(tmp.move('L', Maze));
	        	Q.offer(tmp.move('D', Maze));
	        	Q.offer(tmp.move('R', Maze));
	        }
	        System.out.println("XHAE");
        }   
        sc.close();
	}
}
//현재 모든 공들의 상태를 나타내는 클래스 맵 클래스와 비슷.
class Balls{
	int length; //공 갯수.
	Set<balls> set;	//공들 위치셋
	String trace;	//추적경로.
	
	//공들 구조체.
	class balls{
		final int x;
		final int y;
		balls(int _x,int _y){
			this.x = _x;
			this.y = _y;
		}
		@Override
		public boolean equals(Object o){
			if(!(o instanceof balls))
				return false;
			balls b = (balls)o;
			return this.x == b.x && this.y == b.y;
		}
		
		public int hashCode(){
			return 31*x*y;
		}
	}
	
	//생성자.
	Balls(char[][] Map){
		
		this.set = new HashSet<balls>();
		for (int i = 0; i < Map.length; i++) {
			for (int j = 0; j < Map.length; j++) {
				if(Map[i][j]=='.')
					this.set.add(new balls(i,j));
			}
		}
		this.length = set.size();
		this.trace = "";
	}
	Balls(){
		this.set = new HashSet<balls>();
		this.length = 0;
		this.trace = "";
	}
	
	//메소드//
	//움직이기.
	Balls move(char state, char[][]Map){
		int newX= state=='U' ? -1 : state=='D' ? 1 : 0;
		int newY= state=='L' ? -1 : state=='R' ? 1 : 0;
		Balls next = new Balls();
		
		Iterator<balls> iter = this.set.iterator();
		while(iter.hasNext()){
			balls tmp = iter.next();
			if(Map[tmp.x+newX][tmp.y+newY]=='#'){
				next.set.add(tmp);
				continue;
			}
			
			int nextX = tmp.x;
			int nextY = tmp.y;
			while(Map[nextX+newX][nextY+newY]=='.'){
				nextX += newX;
				nextY += newY;
			}
			if(Map[nextX+newX][nextY+newY]=='O')
				continue;
			
			next.set.add(new balls(nextX,nextY));
		}
		next.length = next.set.size();
		next.trace = this.trace+state;
		return next;
	}
	//같은지 확인.
	@Override
	public boolean equals(Object o){
		if(!(o instanceof Balls))
			return false;
		Balls tmp = (Balls)o;
		
		if(this.length!=tmp.length)
			return false;
		
		if(this.set.equals(tmp.set))
			return true;
		else
			return false;
	}
	
	public int hashCode(){
		return 31*this.length;
	}
	
}

ntopia 8년 전 0

문제 페이지 옆에 보면 '스페셜 저지' 라고 나와있는데요, 이건

"이 문제는 정답이 여러가지일 수 있으니, 당신이 낸 답이 정답의 조건에 맞는지 따로 체크하는 과정을 거치겠다"

뭐 이런 소리입니다

그러니까 첫번째 예제에 대해 RUR을 출력하는 프로그램도 정답으로 인정될거에요

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

문제

문제

출처

ICPC

혹시 정답 체점 여러경우의수 가능한데 제꺼 맞는지 확인부탁드려요..

teahyuk 8년 전 0

ntopia 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말