[1525] 퍼즐 문제 해결 과정 및 최적화
퍼즐 문제는 3×3 보드에 배치된 숫자와 빈칸(0)을 이동시켜, 목표 상태인 123456780을 만드는 최소 이동 횟수를 구하는 문제입니다.
문제 링크: 1525 퍼즐
문제 설명
-
입력:
3×3 보드에 각 칸마다 0(빈칸)과 1~8의 숫자가 주어집니다. -
목표:
빈칸을 인접한 숫자와 교환하여 보드를123456780형태로 만들기 위한 최소 이동 횟수를 구합니다. -
출력:
최소 이동 횟수를 출력하며, 목표 상태를 만들 수 없으면-1을 출력합니다.
첫번째 시도: DFS 접근
먼저 DFS(깊이 우선 탐색)를 이용해 상태를 탐색하는 방식으로 문제를 풀어보았습니다.
아래는 DFS로 구현한 초기 코드입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
public class Main {
private static StringTokenizer st;
private static StringBuilder sb = new StringBuilder();
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static int[][] map = new int[3][3];
private static int[][] targetMap = {{1, 2, 3}, {4, 5, 6}, {7, 8, 0}};
private static int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {-1, 0}};
private static int answer = Integer.MAX_VALUE;
private static Set<String> visitedSet = new HashSet<>();
public static void main(String[] args) throws IOException {
int x = 0, y = 0;
for (int i = 0; i < 3; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < 3; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if (map[i][j] == 0) {
x = i;
y = j;
}
}
}
visitedSet.add(mapToString());
dfs(x, y, 0);
System.out.println(answer == Integer.MAX_VALUE ? -1 : answer);
}
private static String mapToString() {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
sb.append(map[i][j]);
}
}
String result = sb.toString();
sb.setLength(0);
return result;
}
private static void dfs(int x, int y, int cnt) {
if (isSame()) {
answer = Math.min(answer, cnt);
return;
}
for (int i = 0; i < 4; i++) {
int dx = x + dir[i][0];
int dy = y + dir[i][1];
if (dx < 0 || dx >= 3 || dy < 0 || dy >= 3) continue;
int tmp = map[x][y];
map[x][y] = map[dx][dy];
map[dx][dy] = tmp;
if (!visitedSet.contains(mapToString())) {
visitedSet.add(mapToString());
dfs(dx, dy, cnt + 1);
visitedSet.remove(mapToString());
}
map[dx][dy] = map[x][y];
map[x][y] = tmp;
}
}
private static boolean isSame() {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (map[i][j] != targetMap[i][j]) return false;
}
}
return true;
}
}DFS 접근의 문제점
- Stack Overflow:
DFS로 깊은 재귀를 수행하는 과정에서 상태 공간이 매우 넓어져 스택 오버플로우가 발생했습니다.
두번째 시도: BFS로 전환
DFS의 재귀 깊이 문제를 해결하기 위해 BFS(너비 우선 탐색) 방식으로 전환했습니다.
BFS를 사용하면 레벨별로 상태를 탐색하여 최소 이동 횟수를 보장할 수 있습니다.
아래는 BFS로 구현한 초기 코드입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static StringTokenizer st;
private static StringBuilder sb = new StringBuilder();
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static String targetMap = "123456780";
private static int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
private static int answer = Integer.MAX_VALUE;
private static Set<String> visitedSet = new HashSet<>();
public static void main(String[] args) throws IOException {
int x = 0, y = 0;
for (int i = 0; i < 3; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < 3; j++) {
sb.append(st.nextToken());
if (sb.charAt(sb.length() - 1) == '0') {
x = i;
y = j;
}
}
}
String map = sb.toString();
sb.setLength(0);
System.out.println(bfs(map));
}
private static int bfs(String map) {
Queue<String> queue1 = new ArrayDeque<>();
Queue<Integer> queue2 = new ArrayDeque<>();
queue1.add(map);
queue2.add(0);
visitedSet.add(map);
while (!queue1.isEmpty()) {
String curMap = queue1.poll();
int cnt = queue2.poll();
if (curMap.equals(targetMap)) {
return cnt;
}
// 0의 위치를 찾는 과정에서 매 상태마다 문자열 전체를 순회(길이 9)하여 오버헤드 발생
int[] curPoint = findZero(curMap);
for (int i = 0; i < 4; i++) {
int dx = curPoint[0] + dir[i][0];
int dy = curPoint[1] + dir[i][1];
if (dx < 0 || dx >= 3 || dy < 0 || dy >= 3) continue;
// 자리 변경하는 코드가 for문을 9번 순회하여 오버헤드가 큼
for (int j = 0; j < curMap.length(); j++) {
if (j / 3 == curPoint[0] && j % 3 == curPoint[1]) sb.append(curMap.charAt(dx * 3 + dy));
else if (j / 3 == dx && j % 3 == dy) sb.append(curMap.charAt(curPoint[0] * 3 + curPoint[1]));
else sb.append(curMap.charAt(j));
}
String tmp = sb.toString();
sb.setLength(0);
if (!visitedSet.contains(tmp)) {
visitedSet.add(tmp);
queue1.add(tmp);
queue2.add(cnt + 1);
}
}
}
return -1;
}
private static int[] findZero(String map) {
for (int i = 0; i < map.length(); i++) {
if (map.charAt(i) == '0') return new int[]{i / 3, i % 3};
}
return null;
}
}BFS 초기 코드의 문제점
-
빈칸 위치 찾기:
매 상태마다findZero()를 호출하여 문자열 전체(길이 9)를 순회하므로 오버헤드가 발생합니다. -
자리 변경 처리:
문자열 내에서 빈칸과 교환할 숫자를 찾기 위해 9번의 반복과 조건문을 실행하여, 불필요한 연산이 누적됩니다.
최종 코드: 최적화된 BFS
위의 오버헤드를 해결하기 위해 두 가지 개선을 진행했습니다.
-
빈칸 위치 관리:
- 초기 상태 생성 시 빈칸의 인덱스를 계산하여 큐에 함께 저장합니다.
- 매 상태마다 문자열 전체를 순회하지 않고, 빈칸의 인덱스를 직접 활용합니다.
-
문자열 상태 전환 최적화:
- 기존 조건문을 사용하는 for문 대신
toCharArray()를 사용하여 char 배열에서 직접 두 문자의 위치를 교환한 후
new String(char[])를 통해 새로운 상태 문자열을 생성합니다.
- 기존 조건문을 사용하는 for문 대신
최종 코드는 아래와 같습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static StringTokenizer st;
private static StringBuilder sb = new StringBuilder();
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static String targetMap = "123456780";
private static int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
private static int answer = Integer.MAX_VALUE;
private static Set<String> visitedSet = new HashSet<>();
public static void main(String[] args) throws IOException {
int x = 0, y = 0;
for (int i = 0; i < 3; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < 3; j++) {
sb.append(st.nextToken());
if (sb.charAt(sb.length() - 1) == '0') {
x = i;
y = j;
}
}
}
String map = sb.toString();
sb.setLength(0);
System.out.println(bfs(x * 3 + y, map));
}
private static int bfs(int startZeroIdx, String map) {
Queue<String> queue1 = new ArrayDeque<>();
Queue<int[]> queue2 = new ArrayDeque<>(); // {현재 횟수 cnt, 0의 인덱스}
queue1.add(map);
queue2.add(new int[]{0, startZeroIdx});
visitedSet.add(map);
while (!queue1.isEmpty()) {
String curMap = queue1.poll();
int[] curTmp = queue2.poll();
int cnt = curTmp[0];
int zeroIdx = curTmp[1];
if (curMap.equals(targetMap)) {
return cnt;
}
// 0의 위치를 미리 큐에 저장하여 findZero() 오버헤드 제거
int[] curPoint = {zeroIdx / 3, zeroIdx % 3};
for (int i = 0; i < 4; i++) {
int dx = curPoint[0] + dir[i][0];
int dy = curPoint[1] + dir[i][1];
if (dx < 0 || dx >= 3 || dy < 0 || dy >= 3) continue;
// toCharArray()를 사용해 두 문자의 위치를 교환
char[] charArr = curMap.toCharArray();
int curZeroIdx = curPoint[0] * 3 + curPoint[1];
int swapIdx = dx * 3 + dy;
char tmp = charArr[curZeroIdx];
charArr[curZeroIdx] = charArr[swapIdx];
charArr[swapIdx] = tmp;
String nextMap = new String(charArr);
if (!visitedSet.contains(nextMap)) {
visitedSet.add(nextMap);
queue1.add(nextMap);
queue2.add(new int[]{cnt + 1, swapIdx});
}
}
}
return -1;
}
private static int[] findZero(String map) {
for (int i = 0; i < map.length(); i++) {
if (map.charAt(i) == '0') return new int[]{i / 3, i % 3};
}
return null;
}
}결론
-
DFS 접근의 한계:
깊은 재귀 호출로 인한 스택 오버플로우 문제가 발생하여 DFS 방식은 이 문제에 적합하지 않음을 확인했습니다. -
BFS 전환 및 최적화:
BFS를 통해 상태를 레벨별로 탐색하면서 최소 이동 횟수를 보장할 수 있었고,
빈칸 위치를 큐에 함께 저장하고toCharArray()를 활용해 문자열 상태 전환 과정을 최적화함으로써 오버헤드를 크게 줄였습니다.
멋있는 사람 - 일단 하자