[BOJ] 백준 1525번 퍼즐 (Java)

#1525 퍼즐

난이도 :  골드 2

유형 : 그래프 탐색/ BFS/ 문자열/ HashMap

1525번: 퍼즐

▸ 문제

3×3 표에 다음과 같이 수가 채워져 있다. 오른쪽 아래 가장 끝 칸은 비어 있는 칸이다.

1	2	3
4	5	6
7	8

어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다. 우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 것이다. 다음의 예를 보자.

1		3
4	2	5
7	8	6

1	2	3
4		5
7	8	6

1	2	3
4	5
7	8	6

 

1	2	3
4	5	6
7	8

가장 윗 상태에서 세 번의 이동을 통해 정리된 상태를 만들 수 있다. 이와 같이 최소 이동 횟수를 구하는 프로그램을 작성하시오.

 

▸ 입력

세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다.

▸ 출력

첫째 줄에 최소의 이동 횟수를 출력한다. 이동이 불가능한 경우 -1을 출력한다.

 

 

 

 

문제 풀이 🖋 

DFS탐색으로 여러 방향으로 탐색해준다음 최솟값을 출력하면 되는 간단한 문제인줄 알았는데 아니었다. 새로운 접근 방법이 필요했다.

 

📚 조건

   ∙ 3x3 배열, 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다.

   ∙ 빈 칸을 통해 숫자를 이동시켜 정렬된 상태로 최소 이동횟수 출력

 

처음에 DFS탐색을 통해 스택방식으로 가장 최근 경로가 막히면 다시 이전으로 돌아가 탐색을 진행하는 방식으로 접근했지만 엄청 까다로웠다. 왜냐하면 탐색하는 그래프의 값이 계속 변동되었기 때문이다.

 

얕은복사를 하면 이전 상태의 배열을 받아올 수 없어서 처음에만 깊은복사를 하여 다른 4개의 배열로 복사시켰다.

*배열 얕은복사는 둘 다 같은 주소를 참조하여 값이 같이 변동됨. 깊은복사는 아예 다른 두개의 배열이 되어 값 변동 연관 x (참고)

 

당연히 오답이었다. 이런 방식으로 계속 접근하게 되면 하나의 경로를 움직일 때마다 이전 배열의 상태를 저장해주고 불러오고 다시 다른 상태 저장해주고 불러오고... 잘못된 접근방식이었다.

 

틀린코드

public class Main {
	
	static int[][] correct;	
	static int[][] map;
	static boolean[][] check;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		correct = new int[3][3];
		map = new int[3][3];
		
		
		int start_x = 0;
		int start_y = 0;
		for(int i=0; i<3; i++) {
			st = new StringTokenizer(br.readLine());
			
			for(int j=0; j<3; j++) {
				if(i==2 && j==2) {
					correct[i][j] = 0;
				}else {
					correct[i][j] = i*3 + (j+1);
				}
				int num = Integer.parseInt(st.nextToken());
				if(num ==0) {
					start_x = j;
					start_y = i;
				}
				map[i][j] = num;
			}
			
		}
		

		
		for(int d=0; d<4; d++) {
			System.out.println("test"+d);
			check = new boolean[3][3];
			int[][] sample = new int[3][3];
			for(int i=0; i<3; i++) {
				for(int j=0; j<3; j++) {
					sample[i][j] = map[i][j];
				}
			}
			
			int nx = start_x+dx[d];
			int ny = start_y +dy[d];
			
			if(nx <0 || ny <0 || nx>2 || ny>2) continue;
			
			int ch = sample[ny][nx];
			sample[start_y][start_x] = ch;
			sample[ny][nx] =0;
				
			dfs(sample, nx, ny, 1);
		}
		
	}

	
	
	static void dfs(int[][] sample, int x, int y, int move) {
	
		for(int i=0; i<3; i++) {
			for(int j=0; j<3; j++) {
				System.out.print(sample[i][j] +" ");
			}
			System.out.println();
		}
		System.out.println();
		if(compArray(sample)) {
			System.out.println("move" + move);
			return;
		}
//		check[y][x] = true;
		
		
		for(int i=0; i<4; i++) {
			int nx = x +dx[i];
			int ny = y +dy[i];
			
			if(nx <0 || ny <0 || nx>2 || ny>2) continue;
			
			if(sample[y][x] ==0 && !check[ny][nx]) {
				int ch = sample[ny][nx];
				sample[y][x] = ch;
				sample[ny][nx] =0;
				
				check[ny][nx] = true;
				dfs(sample, nx, ny, move+1);
				check[ny][nx] = false;
			}
		}
		
//		check[y][x] = false;
		
		
	}
	
	static boolean compArray(int[][] arr) {
		for(int i=0; i<3; i++) {
			for(int j=0; j<3; j++) {
				if(correct[i][j] != arr[i][j]){
					return false;
				}
			}
		}
		return true;
	}
}

 

 

 

이전 배열의 상태를 어떻게 보관하고 다루느냐가 문제이다. 이 문제만 해결하면 쉽게 풀릴 것이다.

 

좀 더 단순하게 접근해보자!

 

일단 문제에서 그래프의 크기를 3x3으로 고정시켜서 주어졌다. 그러면 1~8로 이루어진 그래프는 고정이고 여기서 왔다갔다 탐색만 하면 되는 것이기 때문에 이를 하나의 String으로 보관해서 다뤄보았다. 

1 0 3
4 2 5
7 8 6

init 초기값 : 103425786
start(0의 위치) : 1

 

그래프의 상태를 배열에 담기에는 너무 메모리 낭비가 심하다. 신기하게 어제 풀은 알고리즘 문제에서 착안한 것이 Map이었다. 다루는 Index값이 너무 크니 Map의 Key로 상태를 저장하면 된다. Value로는 move를 카운트해주자.

 

Map 사용 이점

- 메모리 공간 낭비 줄임

- Key 중복 방지 (키 중복이 되지 않기 때문에 굳이 방문여부 체크를 해주지 않아도 된다.)

 

String으로 그래프를 다루니 0의 위치도 쉽게 알아낼 수 있다.

string.indexOf('0');

 

 

풀이 코드 ✔︎ 

생각해보니 문자열에 대해 다루지 못하면 아예 접근도 못하는 풀이인 것 같다. 그리고 map의 활용성에 대해 다시 한 번 감탄했다. 

import java.io.*;
import java.util.*;

public class Main {
	
	static String correct = "123456780";
	static Map<String, Integer> map = new HashMap<>();
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		String init ="";
		for(int i=0; i<3; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<3; j++) {
				int num = Integer.parseInt(st.nextToken());
				init += num;
			}
		}
	
		map.put(init, 0);
		System.out.println(bfs(init));
	}
	
	static int bfs(String init) {
	
		Queue<String> q = new LinkedList<>();
		q.add(init);
		while(!q.isEmpty()) {
			String pos = q.poll();
			int move =map.get(pos);
			int empty = pos.indexOf('0');
			int px = empty%3;
			int py = empty/3;
			
			if(pos.equals(correct)) {
				return move;
			}
			
			for(int i=0; i<4; i++) {
				int nx = px +dx[i];
				int ny = py + dy[i];
				
				if(nx<0 || ny<0 || nx>2 || ny>2) continue;
				
				int nPos = ny*3 + nx;
				char ch = pos.charAt(nPos);
				String next = pos.replace(ch, 'c');
				next = next.replace('0', ch);
				next = next.replace('c', '0');
				
				if(!map.containsKey(next)) {
					q.add(next);
					map.put(next, move+1);
				}
			}
		}
		return -1;
	}
}