글 읽기 - 반례를 봐도 왜틀린지 모르겠습니다.

windy10928 5년 전 0

일단 3*3 배열을 문자열로 만들어 BFS 탐색 했습니다. visit 체크는 Set<String> 으로 하였습니다.

질문 게시판 보다가 아래 반례가 안돌아 가는 것을 확인했는데, 저는 25가 나오네요...

뭐가 잘못됐는지 모르겠네요 ㅠㅠ

6 4 7
8 5 0
3 2 1

>> 31

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	
	static int[][] map = new int[3][3];
	static HashSet<String> set = new HashSet<>();
	static Queue<String> q = new LinkedList<>();
	static final String GOAL = "123456780";
	static StringBuffer sb = new StringBuffer();
	static int[] d = {1,-1,3,-3};
	static int cnt;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String start = "";
		
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				map[i][j] = sc.nextInt();
				start+= map[i][j];
			}
		}
		
		set.add(start);
		q.offer(start);
		
		boolean ok = false;
		
		while(!q.isEmpty()) {
			
			int size = q.size();
			
			for (int c = 0; c < size; c++) {
				String str = q.poll();
				int idx = str.indexOf('0');	// 0의 위치
				
				if(str.equals(GOAL)) {
					q.clear();
					ok = true;
					break;
				}
				
				// E,W,S,N 탐색
				for (int i = 0; i < 4; i++) {
					int nIdx = idx + d[i];	// 이동하고자 하는 문자열의 index
					
					if(!isRange(nIdx)) continue;
					
					sb = new StringBuffer(str);
					
					// 0과 이동하고자 하는 문자열을 swap 
					sb.setCharAt(idx, str.charAt(nIdx));
					sb.setCharAt(nIdx, '0');
					
					if(set.contains(sb.toString())) continue;
					
					set.add(sb.toString());
					q.offer(sb.toString());
				}
			}
			cnt++;
		}
		System.out.println(ok ? cnt-1 : -1);
	}
	
	public static boolean isRange(int idx) {
		if(idx < 0 || idx >= 9) return false;
		
		return true;
	}
	
}

windy10928 5년 전 0

아 그렇군요... 하하하하... 참 바보같네요 감사합니다~!

master72kl 1년 전 1

아 글 지우셨네 하.........................

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

문제

문제

출처

ICPC

반례를 봐도 왜틀린지 모르겠습니다.

windy10928 5년 전 0

windy10928 5년 전 0

master72kl 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말