글 읽기 - 눈을 씻고 찾아보고 반례를 찾아봤지만..도대체 왜 틀린것인지 알수가 없네요..

sinmi1620 6년 전 0

여러개를 돌려봤는데.. 다 맞는데 제출하면 틀렸다고 나오네요ㅜㅜ 계속 찾아도 도대체 어디가 틀린지 모르겠습니다ㅜㅜ

queue에 레지스터에 저장되는 값들을 넣었고 하나씩 빼고 D,S,L,R연산을 해서 또 레지스터에 넣고 반복했습니다. 그리고 반복하는 과정에서 queue(레지스터)에 뺀 값(=command의 인덱스)에 명령어를 추가했습니다.

만약 1234 -> 2341 이면 command[2341] = command[1234] + 'L' 이런식으로 전의 값 인덱스에다 명령어를 추가해서 바뀐값을 인덱스에 저장했습니다..

역순으로 출력하는 것도 고쳤는데 어디가 문제인지 봐주시면 진짜 감사하겠습니다!!!!

public static void bfs(int A, int B){//ex)A =1234 B 3412
 		Queue<Integer> queue = new LinkedList<Integer>();
		String[] command = new String[10000]; //명령어가 들어갈 것!
		Arrays.fill(command, "");
		boolean[] checked = new boolean[10000]; //반복된 값을 제외하기 위함!
		queue.add(A);
		checked[A] = true;
		while(!queue.isEmpty()){
			int origin = queue.poll(); // 1
			int change;
			char com;
			for(int i=0; i<4; i++){ //방법은 4가지
				change = 0;	
				if(i == 0){//D일때 
					com = 'D';
					change = (origin*2) % 10000;
				}
				else if(i == 1){ //S일때
					if(origin == 0){
						change = 9999;
					}
					else{
						change = origin-1;
					}
					com = 'S';
					
				}
				else if(i == 2){//L일때
					change = (origin%1000)*10 + origin/1000;
					com = 'L';
				}
				else{ //R일때
					change = (origin/10) + (origin%10)*1000;			
					com = 'R';
				}
				
				process(change, command, origin, com, checked, queue);
			}
		}
		String result = command[B];
		for(int i=0; i<result.length(); i++){ // 명령어 역순 출력
			System.out.print(result.charAt((result.length()-1)-i));
		}
		System.out.println();
		
	}
	public static void process(int change, String[] command, int origin, char com, boolean[] checked, Queue<Integer> queue){
		if(!checked[change]){
			queue.add(change);
			command[change] = command[origin] + com; // 원래 값origin에다 새롭게 추가된 명령어 추가
			checked[change] = true;
		}	
	}

sinmi1620 6년 전 0

혹시...String 배열에 명령어를 담는 범위가 초과해서 틀렸다고 나오는 걸까요..? 만약 최악의 경우를 생각해보면 9999부터 0까지 -1로 간다고 하면 명령어 갯수가 9999개일텐데 그럼 초과할거 같긴한ㄷㅔ....하지만.. 이런 명령어는 안나올거같은데.... 도움주세요ㅜㅜ!!

yjna2316 6년 전 0

command[origin] 을 초기화 안해줘서 틀렸다고 나오는거 같아요.

command[origin] = ""; 로 한번 해보세요

초기화 안해서 답이 (예로) DDS 가 아니라 nullDDS 이런식으로 나와서 틀린게 아닐까요?

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

문제

문제

출처

ICPC

눈을 씻고 찾아보고 반례를 찾아봤지만..도대체 왜 틀린것인지 알수가 없네요..

sinmi1620 6년 전 0

sinmi1620 6년 전 0

yjna2316 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말