글 읽기 - 어떤 이유로 틀렸습니다가 나오는 걸까요??

yjna2316 6년 전 0

1차원적으로 생각했습니다.

즉, 문자열에서 9의 위치가 x라 하면, x는 x-1, x+1, x-3, x+3위치에 있는 문자와 자리 교환을 시켰습니다.

그 결과, 20% 쯤 가서 틀렸습니다가 나오는데요, 그 이유를 모르겠습니다. 제 방법대로 해도 나올것 같은데.. ㅜㅜ

반례 찾았습니다.

6 4 7
8 5 0
3 2 1

31이 나와야하는데 저는 25가 나옵니다 도와주세요 ㅜㅜ

public class Puzzle {
  public static final int[] dx = {-3, -1, 1, 3};
  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    int n = 3;
    int start = 0;
    for (int i=0; i<n; i++) {
      for (int j=0; j<n; j++) {
        int temp = sc.nextInt();
        if (temp == 0) {
          temp = 9;
        }
        start = start * 10 + temp;
      }
    }
    Queue<Integer> q = new LinkedList<Integer>();
    HashMap<Integer,Integer> d = new HashMap<Integer,Integer>();
    d.put(start, 0);
    q.add(start);
    while (!q.isEmpty()) {
      int now_num = q.remove(); 
      String now = Integer.toString(now_num);
      int x = now.indexOf('9');
 
      for (int k=0; k<4; k++) {
        int nx = x + dx[k];
        if (nx >= 0 && nx < 9) {
          StringBuilder next = new StringBuilder(now);
          char temp = next.charAt(x);
          next.setCharAt(x, next.charAt(nx));
          next.setCharAt(nx, temp);
          int num = Integer.parseInt(next.toString());
          if (!d.containsKey(num)) {
            d.put(num, d.get(now_num)+1);
            q.add(num);
          }
        }
      }
    }
    if (d.containsKey(123456789)) {
      System.out.println(d.get(123456789));
    } else {
      System.out.println("-1");
    }
  }
}

jh05013 6년 전 5

4번 칸과 3번 칸, 7번 칸과 6번 칸을 교환할 수 없습니다.

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

문제

문제

출처

ICPC

어떤 이유로 틀렸습니다가 나오는 걸까요??

yjna2316 6년 전 0

jh05013 6년 전 5

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말