[백준] 1525번 퍼즐 (C++, JAVA)

1525번: 퍼즐

관리를 편하게 하기 위해 이차원 배열로 되어 있는 값들을 일차원으로 생각하면

123456780 으로 나타내는 게 목표가 된다.

 

빈칸의 상하좌우를 검사해주며 빈칸과 숫자를 교환하고 그 값이 목표와 일치하면

같이 저장되어 있던 횟수를 출력, 큐가 empty할 때까지도 목표를 못 만나면 -1을 출력한다.

 

큐에 값을 집어넣어줄 땐 빈칸과 숫자의 교환을 쉽게 하기 위해서

string 타입으로 숫자를 넣어주는데 이때 0의 위치(빈칸 위치)와

그 숫자까지 가는데 걸린 횟수도 같이 넣어준다.

ex) ("360812745", 2, 이전 수의 횟수 + 1)

 

이차원이었을 때 빈칸의 상하좌우는 일차원일 때에 맞게 바꾸어서 계산해준다.

검사해줄 때 이미 방문한 수는 다시 방문할 필요가 없으므로 방문 체크를 해주어야 하는데

원래 하던 대로 일차원 배열로 방문 체크를 해주려면

최대 인덱스가 visited[876543210]까지 되어서 32MB인 메모리 제한에 걸리게 된다.

그래서 map의 key와 value를 이용해보았다.

key에는 string으로 수를 넣고 value는 bool 타입으로 방문의 유무만 체크해준다.

 

범위를 벗어나는 경우를 처리하는 수식 같은 게 생각 안 나서

그냥 if문으로 상, 하, 좌, 우 에 따라서 좀 무식하게 처리했는데

더 이상 생각하기 싫어서 놔뒀다.

(혹시 좋은 아이디어 있으면 댓글 남겨 주세요..!)

 

< C++ 코드 >

#include <iostream>
#include <queue>
#include <map>
#include <string>
using namespace std;
queue < pair<string, pair<int, int>>> q;
map <string, bool> m;
int dx[4] = { -3, 3, -1, 1 };
int success = -1, idx;
string tmp;
char tmp2;

void Bfs() {
	while (!q.empty()) {
		if (q.front().first == "123456780") {
			success = q.front().second.second;
			break;
		}
		for (int i = 0; i < 4; i++) {
			tmp = q.front().first;
			idx = q.front().second.first + dx[i]; //0의 위치를 기준으로 상하좌우 검색
			if (i == 0 && !(idx >= 0 && idx < 6)) continue; //상
			else if (i == 1 && !(idx >= 3 && idx < 9)) continue; //하
			else if (i == 2 && !(idx >= 0 && idx < 8 && idx != 2 && idx != 5)) continue; //좌
			else if (i == 3 && !(idx >= 1 && idx < 9 && idx != 3 && idx != 6)) continue; //우
			tmp2 = tmp[idx];
			tmp[idx] = tmp[q.front().second.first];
			tmp[q.front().second.first] = tmp2; //위치 교환
			if (!m.count(tmp)) {
				m[tmp] = true;
				q.push(make_pair(tmp, make_pair(idx, q.front().second.second + 1)));
			}
		}
		q.pop();
	}
}

int main() {
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> tmp2;
			if (tmp2 == '0') idx = tmp.size();
			tmp += tmp2;
		}
	}
	q.push(make_pair(tmp, make_pair(idx, 0)));
	Bfs();
	cout << success;
	return 0;
}

 

< JAVA 코드 >

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;

class pair{
	int x, cnt;
	String s;
	pair(int x, int cnt, String s){this.x = x; this.cnt = cnt; this.s = s;}
}

public class BOJ_1525_퍼즐 {
	private static String before = "", goal = "123456780";
	private static int res = -1;
	private static int dx[] = {-3, 3, -1, 1};
	private static Map <String, Boolean> chk = new HashMap<>();
	private static Queue <pair> q = new LinkedList<>();
	
	public static String swap(String s, int a, int b) { // 교환
		StringBuilder sb = new StringBuilder(s);
		char tmp = s.charAt(a);
		sb.setCharAt(a, s.charAt(b));
		sb.setCharAt(b, tmp);
		return sb.toString();
	}
	
	public static void bfs() {
		while(!q.isEmpty()) {
			if(q.peek().s.equals(goal)) { // 현재 모습이 목표 모습이면 성공
				res = q.peek().cnt;
				return;
			}
			for(int i = 0; i < 4; i++) {
				int x = q.peek().x + dx[i], cnt = q.peek().cnt + 1;
				
				// 범위를 벗어나면 이동하지 않는다.
				if (i == 0 && !(x >= 0 && x < 6)) continue; //상
				else if (i == 1 && !(x >= 3 && x < 9)) continue; //하
				else if (i == 2 && !(x >= 0 && x < 8 && x != 2 && x != 5)) continue; //좌
				else if (i == 3 && !(x >= 1 && x < 9 && x != 3 && x != 6)) continue; //우
				
				String s = swap(q.peek().s, q.peek().x, x); // 이동한다.
				if(chk.get(s) != null) continue; // 이동한 모습이 이전에 이미 나왔었으면 무한 반복 상태이므로 넘긴다.
				chk.put(s, true); // 그게 아니라면 방문 표시
				q.offer(new pair(x, cnt, s)); // 새로운 모습에서 0의 위치, 증가된 이동 횟수, 새로운 모습 을 큐에 저장한다
			}
			q.poll();
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++) before += sc.nextInt();
		q.offer(new pair(before.indexOf("0"), 0, before));
		chk.put(before, true);
		bfs();
		System.out.println(res);
	}
}