3*3
2차원 배열에 존재하는 숫자들을 좌상단부터 우하단까지 이어지는 숫자 (1차원 배열, 엄밀히 말하면 String 형)로 표현하는 것이다 String
형태를 HashMap
에 넣어 관리한다. HashMap <String, Integer>
에서 String
은 3x3을 1차원으로 바꾼 모습, Integer
는 이 모습이 되기까지 몇 번의 움직임이 있었는지를 저장한다bfs
를 돌아가면서 ANS="123456780"
와 같거나 큐가 빌 때까지 반복하면서 답을 확인한다 for (int i=0; i<3; i++) {
st=new StringTokenizer (br.readLine());
for (int j=0; j<3; j++) {
sb.append(st.nextToken());
}
}
String형
으로 입력을 받는다StringBuilder sb
를 선언하여 저장하였다Queue
에 처음 맵의 모습(String형으로 나타낸)을 넣고 시작한다HashMap
에 처음 맵의 모습 (init)과 0 (움직인 횟수)를 넣는다 Queue<String> q=new ArrayDeque<>();
q.add(init);
map.put(init, 0);
String pos=q.poll();
int cnt=map.get(pos);
int zero=pos.indexOf('0');
int y=zero/3;
int x=zero%3;
if (pos.equals(ANS))
return cnt;
for (int d=0; d<4; d++) {
int ny=y+dy[d];
int nx=x+dx[d];
if (ny<0 || nx<0 || ny>=3 || nx>=3) continue;
int nPos=ny*3+nx;
char ch=pos.charAt(nPos);
String next=pos.replace(ch, 'x');
next=next.replace('0', ch);
next=next.replace('x', '0');
if (!map.containsKey(next)) {
q.add(next);
map.put(next, cnt+1);
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static final int dy[]= {0,0,1,-1};
static final int dx[]= {1,-1,0,0};
static final String ANS="123456780";
static Map<String, Integer> map=new HashMap<>();
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader (new InputStreamReader (System.in));
StringTokenizer st=null;
StringBuilder sb=new StringBuilder();
for (int i=0; i<3; i++) {
st=new StringTokenizer (br.readLine());
for (int j=0; j<3; j++) {
sb.append(st.nextToken());
}
}
System.out.println(bfs(sb.toString()));
}
private static int bfs (String init) {
Queue<String> q=new ArrayDeque<>();
q.add(init);
map.put(init, 0);
while (!q.isEmpty()) {
String pos=q.poll();
int cnt=map.get(pos);
int zero=pos.indexOf('0');
int y=zero/3;
int x=zero%3;
if (pos.equals(ANS))
return cnt;
for (int d=0; d<4; d++) {
int ny=y+dy[d];
int nx=x+dx[d];
if (ny<0 || nx<0 || ny>=3 || nx>=3) continue;
int nPos=ny*3+nx;
char ch=pos.charAt(nPos);
String next=pos.replace(ch, 'x');
next=next.replace('0', ch);
next=next.replace('x', '0');
if (!map.containsKey(next)) {
q.add(next);
map.put(next, cnt+1);
}
}
}
return -1;
}
}
2차원 배열을 1차원 형태로 나타내고, HashMap에 넣어 관리한다라는 아이디어를 생각하기가 힘들었다