import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
InputStreamReader reader;
BufferedReader br;
int puz[][];
boolean visited[][];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int min_count = Integer.MAX_VALUE;
boolean checkPuz(int[][] A) {
if (A[0][0] != 1) return false;
else if (A[0][1] != 2) return false;
else if (A[0][2] != 3) return false;
else if (A[1][0] != 4) return false;
else if (A[1][1] != 5) return false;
else if (A[1][2] != 6) return false;
else if (A[2][0] != 7) return false;
else if (A[2][1] != 8) return false;
return true;
}
void DFS(int count, int x, int y) {
//System.out.println("DFS("+count+", "+x+", "+y+")");
// 종료조건
if (x==2 && y==2) {
if (checkPuz(puz)) {
//System.out.println("min= "+min_count+", count= "+count);
min_count = Math.min(min_count, count);
}
return;
}
// 재귀호출
//visited[x][y] = true;
for (int i=0; i<4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= 3 || ny < 0 || ny >= 3) continue;
if (visited[nx][ny]) continue;
visited[nx][ny] = true;
// 새 위치로 0이동하고 원래 위치에 숫자이동
int tmp = puz[nx][ny];
puz[nx][ny] = 0;
puz[x][y] = tmp;
DFS(count+1, nx, ny);
// 변경한 값 복구
visited[nx][ny] = false;
tmp = puz[x][y];
puz[x][y] = 0;
puz[nx][ny] = tmp;
}
}
int[][] copyArray(int[][] A) {
for (int i=0; i<3; i++) {
for (int j=0; j<3; j++) {
A[i][j] = puz[i][j];
}
}
return A;
}
int Solve() {
int[][] copiedPuz = new int[3][3];
// 0위치 찾기
for (int i=0; i<3; i++) {
for (int j=0; j<3; j++) {
if (puz[i][j] == 0) {
// 원본 복사해서 넘겨준다.
visited = new boolean[3][3];
//DFS(0, i, j, copyArray(copiedPuz));
//visited[i][j] = true;
DFS(0, i, j);
}
}
}
return min_count;
}
void inputData() throws Exception {
reader = new InputStreamReader(System.in);
br = new BufferedReader(reader);
StringTokenizer st;
puz = new int[3][];
for (int r = 0; r < 3; r++) {
puz[r] = new int[3];
st = new StringTokenizer(br.readLine());
for (int c = 0; c < 3; c++) {
puz[r][c] = Integer.parseInt(st.nextToken());
}
}
}
public static void main(String[] args) throws Exception {
int ans = -2;
Main m = new Main();
m.inputData(); // 입력 받는 부분
ans = m.Solve();// 여기서부터 작성
if (ans == Integer.MAX_VALUE)
System.out.println(-1);
else
System.out.println(ans); // 출력 하는 부분
}
}
<풀이 #2>
BFS를 이용한 완전탐색 문제이다. (나는 DFS를 이용했지만 다른 정답 코드들을 보면 대부분 BFS를 사용했다.)
풀이 #1의 문제점은 0번이 이동하면 값을 swap 해야 하는데 상하좌우로 이동할 때마다 배열의 값이 계속해서 변하는데 이를 계속 복사하면서 넘겨준다면 메모리 낭비가 심할 것이고, 그냥 원본을 사용한다고 다시 돌아왔을 때 값의 무결성을 보장받기 어려운 점이 있다. 이동 후의 전체 맵(3 x 3)을 복사해서 큐에 넣는다면 되겠지만
구글링 했을 때 공통적으로 2가지 핵심 아이디어를 사용했다.
첫번째, 3 x 3 2차원 배열을 1차원 배열로 바꿔서 사용해야 한다.
- 0을 9로 바꿔서 제일 마지막에 자연스럽게 올 수 있게 함.
두번째, Map 자료구조를 사용한다.
- Map의 key 값으로 일차원 배열을 문자열로 바꾼 값, value는 현재까지 이동한 횟수
- map을 업데이트 할 때 새로 만든 문자열이 없을 경우에만 집어넣고 value를 +1해서 put 한다.
세번째, BFS 탐색을 사용한다.
- BFS탐색이기 때문에 상하좌우로 탐색하다보면 먼저 "123456789"가 만들어지면 그게 최소경로이다.
- 왜냐하면 map에 이미 key가 존재하면 value를 업데이트 하지 않기 때문이다.
예) Map을 사용하는 방법 1 2 3 5 0 6 4 7 8 을 입력 받으면 '0'을 '9'로 바꿔서 1차원 배열의 문자열로 만들어 준다. "123596478" 여기서 9와 6을 바꿔주면 key = "123569478", value = 1 이 된다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;
import java.util.Map;
import java.util.HashMap;
public class Main {
InputStreamReader reader;
BufferedReader br;
int puz[][];
boolean visited[][];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int BFS (String start) {
Queue<String> Q = new LinkedList<>();
Map<String, Integer> map = new HashMap<>();
Q.offer(start);
map.put(start, 0);
while (!Q.isEmpty()) {
String now = Q.poll();
int nine_idx = now.indexOf('9');
int x = nine_idx/3; // 9의 1차원 인덱스를 2차원 행 인덱스 계산
int y = nine_idx%3; // 9의 1차원 인덱스를 2차원 열 인덱스 계산
for (int i=0; i<4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
int move_idx = (nx*3)+ny; // (nx, ny)의 1차원 인덱스
if (nx < 0 || nx >= 3 || ny < 0 || ny >= 3) continue;
StringBuilder next = new StringBuilder(now); // now를 변환
// 9가 이동할 위치의 숫자와 swap 하기
char tmp = next.charAt(move_idx);
next.setCharAt(move_idx, '9'); // 이동한 인덱스에 9 넣기
next.setCharAt(nine_idx, tmp); // 9가 있던 자리에는 tmp 값 넣기
// map에 만든 문자열이 없으면 방문하지 않은 지역이므로 업데이트 한다
String next_num = next.toString();
if (!map.containsKey(next_num)) {
Q.offer(next_num);
map.put(next_num, map.get(now)+1);
}
}
}
// 정답 확인
if (map.containsKey("123456789")) {
return map.get("123456789");
} else {
return -1;
}
}
int Solve() {
// 입력받은 수 중 '0'을 '9'로 교체해서 문자열로 변환
StringBuilder sb = new StringBuilder();
for (int i=0; i<3; i++) {
for (int j=0; j<3; j++) {
if (puz[i][j] == 0) {
sb.append('9');
} else {
sb.append(Integer.toString(puz[i][j]));
}
}
}
// 처음 입력받은 순서로 만든 문자열로 BFS 탐색 시작
int min_count = BFS(sb.toString());
return min_count;
}
void inputData() throws Exception {
reader = new InputStreamReader(System.in);
br = new BufferedReader(reader);
StringTokenizer st;
puz = new int[3][];
for (int r = 0; r < 3; r++) {
puz[r] = new int[3];
st = new StringTokenizer(br.readLine());
for (int c = 0; c < 3; c++) {
puz[r][c] = Integer.parseInt(st.nextToken());
}
}
}
public static void main(String[] args) throws Exception {
int ans = -2;
Main m = new Main();
m.inputData(); // 입력 받는 부분
ans = m.Solve();// 여기서부터 작성
System.out.println(ans); // 출력 하는 부분
}
}
<풀이 #3>
꼭 HashMap을 사용해야 할까? 꼭 문자열로 변환을 해야지 풀리는 문제일까?
궁금증이 들어서 풀이 #2를 base로 해서 2차원 배열 상태로 놔두면서 한번 풀어보았다.
* 변경점
1. 2차원 배열 형태를 1차원 배열 문자열로 변환하는 부분을 삭제
- 2차원 배열 그대로 깊은 복사를 해서 큐에 넣는다.
- 0이 이동하면 이동한 상태의 배열을 그대로 복사해서 class Node에 넣는다.
2. HashMap을 사용하지 않고 유효성 검증하는 함수를 만들어서 사용
- 0이 (2, 2) 위치에 도달하면 check 함수를 호출해서 현재 숫자의 위치가 유효한지 검사한다.
- 유효하면 count를 리턴한다.
3. BFS탐색이 끝날 때 까지 return이 안 일어나면 길이 없는 것으로 판단하여 -1을 리턴한다.
4. 0이 이동할 때 마다 값이 swap이 발생해서 전체 맵의 배치가 달라진다. 따라서 방문배열을 사용하지 않는다.
하지만, 결과는 메모리 초과가 발생했다. 방문 배열을 사용하지 않기 때문에 많은 경우의 수가 발생하고, 3x3 배열이라도 경우의 수가 많으니 많은 메모리가 소모된 것으로 보인다.
댓글