백준 1525 : 퍼즐

https://www.acmicpc.net/problem/1525

1525번: 퍼즐

[ 문제풀이 ]

bfs를 수행하여 0을 옮길 수 있는 모든 경우를 탐색해주면 된다. 퍼즐의 상태를 쉽게 관리하기 위해 3x3 배열이 아닌 1차원의 문자열 형태로 관리하였다.

퍼즐의 상태와 중복 방문을 관리해줄 방법만 생각해낸다면 쉽게 해결할 수 있을 것이다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {

	static final String goal = "123456780";
	static int ans;
	static Set<String> set;

	static int[][] dir = {{1,3},{-1,1,3},{-1,3},{-3,1,3},{-3,-1,1,3},{-3,-1,3},{-3,1},{-3,-1,1},{-3,-1}};

	static class Node {
		int cnt, zeroIdx;
		String state;

		public Node(int cnt, int zeroIdx, String state) {
			this.cnt = cnt;
			this.zeroIdx = zeroIdx;
			this.state = state;
		}
	}

	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))){
			ans = -1;
			set = new HashSet<>();
			StringBuilder start = new StringBuilder();
			int zeroIdx = 0;
			for (int i = 0; i < 3; ++i) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				for (int j = 0; j < 3; ++j) {
					start.append(st.nextToken());
					if (start.charAt(start.length() - 1) == '0') {
						zeroIdx = start.length() - 1;
					}
				}
			}
			
			bfs(new Node(0, zeroIdx, start.toString()));
			
			bw.write(ans + "\n");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	public static void bfs(Node start) {
		Queue<Node> q = new LinkedList<>();
		q.offer(start);
		set.add(start.state);

		while (!q.isEmpty()) {
			Node n = q.poll();
			
			if (n.state.equals(goal)) {
				ans = n.cnt;
				return;
			}
			
			for (int d = 0; d < dir[n.zeroIdx].length; ++d) {
				StringBuilder sb = new StringBuilder(n.state);
				sb.setCharAt(n.zeroIdx, sb.charAt(n.zeroIdx + dir[n.zeroIdx][d]));
				sb.setCharAt(n.zeroIdx + dir[n.zeroIdx][d], '0');

				String s = sb.toString();
				if (set.contains(s)) continue;
				set.add(s);
				q.offer(new Node(n.cnt + 1, n.zeroIdx + dir[n.zeroIdx][d], s));
			}
		}
	}
}