[백준] 1525 퍼즐 - BFS(너비우선탐색) + HashMap + StringBuilder JAVA

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

1525번: 퍼즐

코드설명

BFS와 HashMap , StringBuilder를 활용하는 문제입니다.

 

문제에서 해당 퍼즐을 0 을 옮길때마다 깊은복사를 진행하면서 새로운 Stack 안에 계속해서 파고들어가며 DFS를 실행해도 되겠지만, 해당 방향으로 할 경우 너무 복잡해집니다.. 

 

그대신에 HashMap을 활용합니다. HashMap에는 "123456780" 을 Key값으로 사용하고 Value 값으로는 몇번의 이동만으로 갔는지 Integer 정수형으로 저장시킵니다. 일종의 BFS에서 Node Class에 필드에 Cnt를 넣은 상태라고 보면 됩니다.

HashMap을 이런식으로 사용하는것이 인상깊었습니다. DFS에서 하나씩 들어가는 Stack Frame 처럼 사용합니다.

 

1. 처음에 입력받은 값을 HashMap에 저장합니다. HashMap의 키는 퍼즐 상태를 나타내는 문자열이고, 값은 해당 상태까지의 최소 이동 횟수입니다.
2. BFS를 사용하여 퍼즐을 푸는데, 큐에 초기 상태를 넣고, 큐가 빌 때까지 다음을 반복합니다.
   a. 큐에서 값을 하나 꺼내고, 0의 위치를 찾습니다.
   b. 만약 현재 상태가 목표 상태라면, 최소 이동 횟수를 저장하고 종료합니다.
   c. 상하좌우로 0과 위치를 바꿔가면서 큐에 삽입합니다.
   d. 새로운 상태가 HashMap에 없으면 큐에 추가하고, 최소 이동 횟수를 업데이트합니다. 이떄 몇번만에 해당 값을 찾았는지 HashMap의 Value에 저장해두기 위하여 이전 값의 HashValue를 호출하여 + 1 시켜 저장합니다. 

최종적으로 목표 상태까지의 최소 이동 횟수를 출력합니다.

코드

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 int N, M;
	public static int[][] map;
	public static int answer = Integer.MAX_VALUE;
	
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
	public static HashMap<String, Integer> hashmap = new HashMap<String, Integer>();
	public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//    	StringTokenizer st = new StringTokenizer(br.readLine());

    	for(int i=0;i<3;i++) {
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		for(int j=0;j<3;j++) {
    			sb.append(Integer.parseInt(st.nextToken()));
    		}
    	}
    	
		hashmap.put(sb.toString(), 0);
		simulate(sb.toString());
    	
    	if(answer == Integer.MAX_VALUE) {
    		System.out.println("-1");
    	}else {
    		System.out.println(answer);    		
    	}
    	
    	
	}
	
	public static void simulate(String startStr) {
		
		Queue<String> q = new LinkedList<>();
		q.offer(startStr);
		
		while(!q.isEmpty()) {
			String temp = q.poll();
			int tempZeroIdx = temp.indexOf("0"); //0의 위치를 찾습니다.

			if(temp.equals("123456780")) {
				answer = hashmap.get("123456780");
				return ;
			}
			
			for(int dir = 0;dir<4;dir++) { //상하좌우로 이동할 것 입니다.
				int nr = tempZeroIdx/3 + dx[dir];
				int nc = tempZeroIdx%3 + dy[dir];
				if(nr < 0 || nr >= 3 || nc < 0 || nc >= 3) continue;
				
				int nTempZeroIdx = nr * 3 + nc;
				StringBuilder nSb = new StringBuilder(temp);
				char saveWords = nSb.charAt(nTempZeroIdx);
				nSb.setCharAt(nTempZeroIdx, '0');
				nSb.setCharAt(tempZeroIdx, saveWords);
				
				if(hashmap.containsKey(nSb.toString()) == false) { //처음으로 들어온 값일경우에만
					q.offer(nSb.toString());
					hashmap.put(nSb.toString(), hashmap.get(temp) + 1);
				}
			}
		}
	}
	
}