퍼즐 [백준 1525][JAVA][골드2][BFS][String][완전탐색]

 

[광고 누르면 오늘의 행운 상승!!]

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

1525번: 퍼즐

너무 어려워서 블로그를 보고 이해하는데 노력했다.
java에서 제공하는 함수들을 잘 활용해서 푼 블로그가 있길래 덕분에 많이 배운 것 같다.

1. 참고사항

- 2차원 배열을 하나의 정수로 표현한다.
- MAP을 이용하여 정수와 이동횟수를 관리한다.
- String.valueOf(int N) : int N을 String으로 변환해준다.
- StringBuilder.setCharAt -> 특정 위치에 char를 삽입할 수 있다.
- String.indexOf(String s) -> s가 위치한 인덱스를 반환한다.
- map.containsKey(String s) -> map이 s라는 key를 갖고있다면 true.
- int row = idx / 3; // idx 가 2차원배열에서 몇 번째 행인지 계산
- int col = idx % 3; // idx 가 2차원배열에서 몇 번째 열인지 계산

2. 구현

- start 변수에 2차원배열을 하나의 정수로 바꾸어 담는다.
- map에 초기 정수와 횟수를 담는다.
- bfs를 시작한다
- 4방향으로 탐색하면서 자신과 바꿀 위치를 스왑하고 map에 중복되지 않으면 담는다.
- 반복

 

package Study9;

import java.io.*;
import java.util.*;
 
public class 퍼즐 {
	static int[] dx = {0, 0, 1, -1};
	static int[] dy = {1, -1, 0, 0};
    static Queue<Integer> q = new LinkedList<>();
    static Map<Integer, Integer> m = new HashMap<>();
    
    public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int start = 0;
		for (int i = 0; i < 3; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 3; j++) {
				int k =  Integer.parseInt(st.nextToken());
				 if(k == 0) { //0을 9로 바꿈
	                    k = 9;
	             }
	             start = (start*10) +k; //2차원배열을 하나의 정수로 나타내기 위해서
			}
		}
   
        m.put(start, 0);
        q.add(start);
        
        bfs();
     
        if(m.containsKey(123456789)) {
            System.out.println(m.get(123456789));
        }
        else
            System.out.println(-1);
    }


	private static void bfs() {
		/*
		String.valueOf(int N) -> int N을 String으로 변환해준다.
        StringBuilder.setCharAt -> 특정 위치에 char를 삽입할 수 있다.
       	String.indexOf(String s) -> s가 위치한 인덱스를 반환한다.
       	map.containsKey(String s) -> map이 s라는 key를 갖고있다면 true.
       	int row = idx / 3; // idx 가 2차원배열에서 몇 번째 행인지 계산
        int col = idx % 3; // idx 가 2차원배열에서 몇 번째 열인지 계산
        int start = 0;
        
        for (int i = 0; i < 3; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 3; j++) {
				int k =  Integer.parseInt(st.nextToken());
				 if(k == 0) { //0을 9로 바꿈
	                    k = 9;
	             }
	             start = (start*10) +k; //2차원배열을 하나의 정수로 나타낸다. (ex: 123456789)
			}
		}
       	
        */
	   while(!q.isEmpty()) {
            int nowNum = q.poll();
            String now = String.valueOf(nowNum); 
            int nine = now.indexOf("9"); //9의 인덱스를 찾는다.
            int row = nine / 3; // 9가 2차원배열에서 몇 번째 행인지 계산
            int col = nine % 3; // 9가 2차원배열에서 몇 번째 열인지 계산
            
            for(int i=0; i<4; i++) {
                int nx = row + dx[i]; 
                int ny = col + dy[i]; 
                int move = nx*3+ny; //이동할 상하좌우의 1차원배열에서의 인덱스
                
                if (nx < 0 || nx >= 3 || ny < 0 || ny >= 3) continue; 
                
                StringBuilder next = new StringBuilder(now);
                //9와 이동할 상하좌우 스왑하기
                char temp = next.charAt(move);
                next.setCharAt(move, '9'); //이동할 인덱스에 9를
                next.setCharAt(nine, temp); //원래 9자리에 이동한 곳의 수를
                
                int nextNum = Integer.parseInt(next.toString());
                if(!m.containsKey(nextNum)) { //맵에 몇 번이동했는지 저장
                    m.put(nextNum, m.get(nowNum)+1);
                    q.add(nextNum);
                }
                
            }
        }
	}
}

3. 참고 블로그

https://dundung.tistory.com/67

백준 1525 퍼즐 Java