[백준 1525번][Java] 퍼즐 - 그래프 상태 비트마스킹하기

www.acmicpc.net/problem/1525

1525번: 퍼즐

풀이를 둘러보니 상태를 저장하는 방법이 꽤 여러 가지였습니다. 

각 요소의 값이 모두 1자리기 때문에 문자열이나 그냥 정수로 상태를 표현한 풀이도 가능합니다. 하지만 값이 한 자리를 넘어가는 순간 값들을 분리해야 되기 때문에 다른 방법이 필요할겁니다. 

 

비트마스킹은 입력의 범위가 크지 않다면 일반적인 대안이 될 수 있습니다. 

 

이 문제의 경우 0~9까지의 수를 표현하기 위해 4자리의 비트가 필요합니다. 수를 모두 9개이므로 36비트가 필요하겠네요.

자바 int 자료형은 32비트라서 안되고 long 자료형을 써야 됩니다(64비트).

 

아래 코드에서 눈여겨 볼점은

 

1. 방문 여부를 HashSet을 이용해서 한다는 점 

 

배열을 사용하는 것보다 1을 사용하면 메모리를 좀 더 아낄 수 있습니다(최악의 경우에는 메모리 사용이 동일하겠지만).

 

2. 상태 정보 <-> 2차원 배열 : 서로를 변환하는 연산이 있다는 점

 

번거롭게 상태 정보를 다시 배열로 변환하는 과정을 거치는 이유는 비트만을 이용해서 빈 칸을 상하좌우로 스왑하는게 상당히 귀찮기 때문입니다. 배열로 변환한 뒤 다시 비트로 변환하는게 훨씬 편하죠. 그리고 다른 연산을 위해 puzzle 배열을 다시 복구하는 것도 눈여겨 봐야 됩니다.

 

 

참고) long 자료형의 비트연산에 참여하는 다른 변수들도 왠만하면 long으로 통일하는게 좋습니다. 값이 달라질 수 있기 때문에. 

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

/*
퍼즐
https://www.acmicpc.net/problem/1525
 */
public class Main {
	static long[][] puzzle = new long[3][3];
	public static void main(String[] args) throws IOException {
//		InputReader reader = new InputReader("testcase.txt");
		InputReader reader = new InputReader();

		for (int i = 0; i < 3; i++) {
			StringTokenizer st = new StringTokenizer(reader.readLine());
			for (int j = 0; j < 3; j++) {
				puzzle[i][j] = Long.parseLong(st.nextToken());
			}
		}
		long[][] destArr = {
				{1,2,3},
				{4,5,6},
				{7,8,0}
		};
		long destState = getStatus(destArr);
		int ret = bfs(destState);
		System.out.println(ret);
	}

	static int[] dr = {1,-1,0,0};
	static int[] dc = {0,0,1,-1};

	private static int bfs(long destState) {
		Queue<Node> q = new ArrayDeque<>();
		HashSet<Long> visitedStatus = new HashSet<>();
		long firstState = getStatus(puzzle);
		if(firstState == destState) return 0;
		visitedStatus.add(firstState);
		q.add(new Node(firstState,0));

		while(!q.isEmpty()) {
			Node here = q.poll();
			//puzzle에 state를 그리고 빈칸의 위치를 반환
			Point currentZero = writeStateOnArray(here.state, puzzle);

			for (int i = 0; i < 4; i++) {
				Point nextZero = new Point(currentZero.row + dr[i],  currentZero.col + dc[i]);
				if(nextZero.isRange()) {
					//이동이 가능한 점이라면 swap
					swap(currentZero, nextZero, puzzle);
					long nextState = getStatus(puzzle);
					//다음 요소를 위해 변화 복구
					swap(nextZero, currentZero, puzzle);
					//도착지 상태와 동일한 경우
					if(nextState == destState) return here.dist + 1;
					//방문하지 않은 경우 hashSet에 저장
					if(!visitedStatus.contains(nextState)) {
						q.add(new Node(nextState, here.dist+1));
						visitedStatus.add(nextState);
					}
				}
			}//for
		}//while

		return -1;
	}

	private static void swap(Point a, Point b, long[][] puzzle) {
		long temp = puzzle[a.row][a.col];
		puzzle[a.row][a.col] = puzzle[b.row][b.col];
		puzzle[b.row][b.col] = temp;
	}

	//long형 정수에 저장된 state를 puzzle 배열에 복원하고 zero의 위치 반환
	private static Point writeStateOnArray(long state, long[][] puzzle) {
		int order = 0;
		long fourFullBit = (1 << 4) - 1;
		Point zero = null;
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				long num = state & (fourFullBit << (4*order));
				puzzle[i][j] = (num >> (4*order));
				order++;
				if(puzzle[i][j] == 0) { zero = new Point(i,j); }
			}
		}

		return zero;
	}
	
	//puzzle 배열의 상태를 비트마스킹한 long형 정수 반환	
	private static Long getStatus(long[][] puzzle) {
		long s = 0l;
		int order = 0;
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				s |= puzzle[i][j] << (4*order);
				order++;
			}
		}
		return s;
	}
}
class Point {
	int row, col;
	public Point(int row, int col) {
		this.row = row;
		this.col = col;
	}

	public boolean isRange() {
		if(row < 0 || row >= 3 || col < 0 || col >= 3) return false;
		return true;
	}
}
class Node {
	long state;
	int dist;

	public Node(long state, int dist) {
		this.state = state;
		this.dist = dist;
	}

	@Override
	public boolean equals(Object o) {
		if (this == o) return true;
		if (o == null || getClass() != o.getClass()) return false;

		Node node = (Node) o;

		return state == node.state;
	}

	@Override
	public int hashCode() {
		return (int) (state ^ (state >>> 32));
	}
}

class InputReader {
	private BufferedReader br;

	public InputReader() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	public InputReader(String filepath) {
		try {
			br = new BufferedReader(new FileReader(filepath));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	public List<Character> readLineIntoCharList() throws IOException {
		List<Character> l = new ArrayList<>();
		while(true) {
			int readVal = br.read();
			if(readVal == '\n' || readVal == -1) break;
			l.add((char)readVal);
		}
		return l;
	}

	public boolean ready() throws IOException {
		return br.ready();
	}

	public String readLine() throws IOException {
		return br.readLine();
	}
	public int readInt() throws IOException {
		return Integer.parseInt(readLine());
	}
	public Long readLong() throws IOException {
		return Long.parseLong(readLine());
	}
}