백준 1525 <퍼즐>

이 문제는 어떻게 하면 메모리를 효과적으로 관리하면서 방문처리를 해주는가에 집중이 필요한 문제였다.

 

그래서 나는 이문제의 맵의 상태를 String으로 만들어 hashmap에 관리함으로써 메모리를 줄여 나갔다.

 

문제 풀이

1. 각각의 맵의 상태를 String으로 저장해서 count와 함께 현재 비어있는 위치를 보관하는 class를 선언했다.
2. 비어있는 위치에서 4방향으로 검색한 뒤 string으로 만들고 hashmap에 저장되어있으면 패스하고 저장 안 되어있으면 hashmap에 넣어주고 queue에도 넣어주었다.

현재 상태를 배열그대로 저장하게 되면 메모리를 많이 차지하기 때문에 줄여주었다.

 

다음 방향 숫자와 현재 위치의 0을 바꿔주고 string으로 출력하는 과정이다.

이러한 과정이 계속 반복되고 결과와 같다면 result 값을 바꿔주고 return;

 

어려운 문제는 아니었지만 시간초과가 아닌 메모리 초과 관리가 필요한 문제였다.

 

전체 코드

 

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	public static class move {
		String s;
		int count;
		Point p;

		public move(String s, int count, Point p) {
			super();
			this.s=s;
			this.count = count;
			this.p = p;
		}
	}

	static Queue<move> q;
	static HashMap<String, Boolean> h;
	static int map[][], dir[][] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }, result = -1;
	static String results = "";

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		map = new int[3][3];
		h = new HashMap<String, Boolean>();
		q = new LinkedList<move>();
		for (int i = 0; i < 3; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 3; j++) {
				results += st.nextToken();
				map[i][j] = i * 3 + j + 1;
			}
		}
		map[2][2] = 0;
		String nexts = "123456780";
		if (!nexts.equals(results)) {
			h.put(nexts, true);
			q.add(new move(nexts, 0, new Point(2, 2)));
			bfs();
		}
		else
			result=0;
		System.out.println(result);

	}

	private static void bfs() {
		// TODO Auto-generated method stub
		while (!q.isEmpty()) {
			move next = q.remove();
			for (int i = 0; i < 4; i++) {
				int x1 = next.p.x + dir[i][0];
				int y1 = next.p.y + dir[i][1];
				if (x1 < 0 || x1 >= 3 || y1 < 0 || y1 >= 3) {
					continue;
				}
				String nexts = visit(x1, y1, next.p,next.s);
				if(nexts.equals(results)) {
					result=next.count+1;
					return;
				}
				if (h.get(nexts) != null) {
					continue;
				}
				h.put(nexts, true);
				q.add(new move(nexts, next.count + 1, new Point(x1, y1)));
			}
		}

	}

	private static String visit(int x1, int y1, Point p,String s1) {
		// TODO Auto-generated method stub
		String s = "";
		int k1=x1*3+y1;
		int k2=p.x*3+p.y;
		for (int i = 0; i < s1.length(); i++) {
			if(i==k1) {
				s+=s1.charAt(k2);
			}
			else if(i==k2) {
				s+=s1.charAt(k1);
			}
			else
				s+=s1.charAt(i);
		}
		return s;
	}
}