[백준] 1525 - 퍼즐 (JAVA)

소요시간

20분 보다가 BFS 로 풀어야 하는 것은 알았는데 어떤 방식으로 접근해야 할지 모르겠어서 다른 분들의 블로그를 참고했다.
그렇게 10분 정도 풀이를 보고 직접 구현해봤다.
30분 걸렸고, 그렇게 도합 1시간이 걸렸다.

사용한 자료구조 & 알고리즘

해시맵, BFS 를 사용했다. 해시맵은 bfs 의 visited 배열 같은 요소로, 내가 탐색하는 것이 이전에 이미 탐색했던 숫자라면 continue 해주는 용도로 사용.
전체적인 알고리즘은 BFS 를 사용해서 완전탐색했다.

풀이과정

1. 우선 2차원 배열을 편의상 1줄로 만들어준다.
2. 0의 위치를 찾는다. 0을 9로 변경해준다.
3. BFS 탐색 시작!
4. 1줄로 만든 것을 3으로 나눈것이 행이고, 3으로 나눈 나머지가 열이다. 9의 위치를 찾는다.
5. 이미 한 번 찾아온 곳이라면 continue, 만약 그것의 size가 3이상이거나, 0미만이라고 해도 continue.
6. 필터링 한 곳이 한 번도 찾아온 곳이 아니므로, 이전의 9가 있었던 인덱스의 값과 교환한다.
7. 맵에 이 값이 찾아왔었고, 이제 다시 찾아오지 않을 것이므로 put한다. 이 때 count+1 로 같이 넣어준다.
8. queue 에 변형된 숫자를 넣어준다.
9. 만약 이제 여기서 queue에서 poll 된 값이 123456789 라면 탐색 종료. 정답을 찾은것.
10. 모든 경우를 다 따져봐도 123456789가 되지 않는다면 변형 불가하다. 탐색 종료.

예외 처리

1. 우선 왜 1234567890 이 아니라 123456789로 놓는지에 대한 이해가 필요하다. 0이 4번째 인덱스에 있고, 이를 0번째 인덱스와 교환한다면 첫 자리가 0이 될 수 있다. 012345678 의 형태가 될 수 있고,이를 integer 로 표현한다면 12345678 이다. 우리는 0의 값이 손실되는 것을 방지해야한다. 그렇기에 9로 대체했다.
2. 처음 제출했을 때 메모리 초과가 났다. 그래서 쭉 고민해봐도 답을 찾을 수 없었는데 내가 JAVA 15를 써서 그렇다. 문제 아래를 보면 JAVA 8과 11은 256MB, 다른 것은 32MB 였다. 8로 바꾸고 제출하자마자 성공했다.

소스코드

import java.io.*;
import java.util.*;
import java.math.BigInteger;


public class Main{

	static int arr[][]=new int[3][3];
	static int yy[]= {-1,1,0,0};
	static int xx[]= {0,0,-1,1};

	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int number=0;

		for(int i=0;i<3;i++) {
			String line[]=br.readLine().split(" ");
			for(int j=0;j<3;j++) {
				arr[i][j]=Integer.parseInt(line[j]);
				if(arr[i][j]==0) arr[i][j]=9;
				number=number*10+arr[i][j];
			}
		}
		
		System.out.println(bfs(number));


	}
	public static int bfs(int number) {
		HashMap<Integer,Integer> map =new HashMap<>();
		Queue<Integer> queue=new LinkedList<>();
		map.put(number,0);
		queue.add(number);
		int answer=123456789;
		
		while(!queue.isEmpty()) {
			int before=queue.poll();
			if(before==answer) {
				return map.get(answer);
			}
			String temp=Integer.toString(before);
			
			int index=0;
			for(int i=0;i<temp.length();i++) {
				if(temp.charAt(i)-'0'==9) {
					index=i;
					break;
				}
			}
			int y=index/3;
			int x=index%3;
			
			for(int i=0;i<4;i++) {
				int nextY=y+yy[i];
				int nextX=x+xx[i];
				int changeIndex=nextY*3+nextX;
				if(nextY<0||nextX<0||nextY>=3||nextX>=3)
					continue;
				StringBuilder sb=new StringBuilder(temp);
				char changeCh=temp.charAt(changeIndex);
				sb.setCharAt(index, changeCh);
				sb.setCharAt(changeIndex, '9');
				if(map.containsKey(Integer.parseInt(sb.toString()))) continue;
				int next=Integer.parseInt(sb.toString());
				
				map.put(next,map.get(before) +1);
				queue.add(next);
				
				
				
			}
			
			
		}
		

		return -1;
	}
}

결과

회고 & 새롭게 알게 된 것

1. BFS 의 새로운 응용법
2. 그리고 n*n 의 map이 있을때 n으로 나누면 행, n으로 나눈 나머지가 열이라는 사실
3. StringBuilder의 setCharAt 메소드. 이 메소드를 잘 쓰면 유용할 것 같다고 생각한다.
4. 이전까지는 queue를 2차원 배열로 쓰면서 value와 count 를 세줬었는데, 여기서는 HashMap에서 count를 세어주는 새로운 방식이었다. 오.. 이것도 새로웠다.
5. 2차원 맵을 1차원 맵으로 변형해서 볼 수 있다는 사실. 와... 생각도 못했다.

1문제를 푸는데 이렇게 많은 것을 알아간다니 진짜 알차다.
매번 똑같은 유형의 문제 말고 이런 이색적인 문제를 푸는 것이 즐겁다.

하루에 백준 1문제 이상 푸는 것을 목표로하고 있다.

https://solved.ac/profile/anwlro0212