글 읽기 - 틀린 이유를 모르겠습니다!!

huds093 6년 전 0

100%까지 실행되고 나서 틀렸다고 뜹니다.

아무리 봐도 틀린 곳을 모르겠습니다.

해시맵 이용해서 string으로 key잡고 카운트를 해주기 위해서 int값을 value로 했습니다.

--------------------------------

방금 약간의 수정을 했더니 맞았습니다. 메인에서 /**/부분을 추가했습니다. 그리고 BFS에서 출력하지 않고 str이 123456780이면 return만 하게 했습니다.

차이가 없는 것 같은데 왜 결과가 다를까요..?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
public class Main {

	static final int N = 3;
	static Queue<String> q = new LinkedList<>();
	static HashMap<String, Integer> h = new HashMap<>();

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

		for(int i=0; i<N; i++) {
			String s[] = br.readLine().split(" ");
			for(int j=0; j<N; j++) {
				String tmp = s[j];
				start += tmp;
			}
		}
		BFS(start);
        /*
        if(h.containsKey("123456780")) {
			System.out.println(h.get("123456780"));
		}
		else
			System.out.println("-1");
        */
	}
	private static void BFS(String start) {
		int[] dx = {-1,0,1,0}, dy = {0,1,0,-1};
		q.add(start);
		h.put(start, 0);

		while(!q.isEmpty()) {

			String s = q.poll();

			int w = s.indexOf("0");
			int x = w/3;
			int y = w%3;

			for(int i=0; i<4; i++) {

				int nx = x + dx[i];
				int ny = y + dy[i];

				if(nx<0 || ny<0 || nx>N-1 || ny>N-1)		continue;

				String str = s;
				char a = str.charAt(w);
				char b = str.charAt(nx*3+ny);
				str = str.replace(a, 'a');
				str = str.replace(b, 'b');
				str = str.replace('a', b);
				str = str.replace('b', a);

				if(!h.containsKey(str)) {
					q.offer(str);
					h.put(str, h.get(s)+1);
					
					if(str.equals("123456780")) {
						System.out.println(h.get(str));
						System.exit(0);
					}	
				}
			}
		}
		System.out.println("-1");
		System.exit(0);
	}
}

wello_horld 6년 전 0

음... 보통 100%면 최소값 혹은 최대값에서 문제가 생기는 경우가 많습니다. 저는 저 문제를 못 풀어서 직접적인 도움은 못 드리지만, 그런 경우를 한번 따져 보시는게 어떨까요?

djm03178 6년 전 0

BFS가 시작하자마자 처음 상태를 방문 체크에 넣었으니, 앞으로 그 상태는 영영 다시 방문하지 못합니다. 그리고 큐에서 꺼낸 후에 체크를 하는 것이 아니라 다음 큐에 넣을 때 체크를 하기 때문에 처음 상태는 단 한 번도 확인되지 못합니다.

csh6103 6년 전 0

1 2 3

4 5 6

7 8 0

huds093 6년 전 0

세 분 정말 너무 감사드려요!!! 그 경우는 아예 생각도 안 했었네요...

감사합니다!!

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

문제

문제

출처

ICPC

틀린 이유를 모르겠습니다!!

huds093 6년 전 0

wello_horld 6년 전 0

djm03178 6년 전 0

csh6103 6년 전 0

huds093 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말