[BOJ] 백준 1525 퍼즐 (JAVA)

BFS + HashMap 방문처리!

📑 문제

백준 1525 퍼즐

 

---

🌱 아이디어

"고민해도 안 나온다면 답지보고 내 것으로 만들자"

 

이 문제는 내가 여태까지 풀어왔던 알고리즘 지식 + 기법(?)으로  어떻게는 해결해보려고 했으나 다 실패했다.

우울해하면서 결국 검색을 통해 코드를 봤다.

HashMap으로 BFS 방문처리를 하는 코드였지만 정말 특이한 부분이 있었다

 

1차원 배열의 인덱스(문자열)를 2차원 배열로 변경해서 경로 이동후 다시 1차원 배열(문자열)로 변환 후

HashMap을 통해 문자열을 저장하는 방법이었다

 

예를 들어

문자열 str = "123456789"

3*3 2차원 배열로 나타낼 때

 

1차원 배열 -> 2차원 배열

Y = 3 / 3

X = 3 % 3

 

숫자 4는

idx ( 1 , 0 )에 위치하게 된다

만약 X 축으로 +1을 해주고

 

idx ( 1 , 1 )로 이동했다면.

다시 1차원 배열로 변경해 보자!

 

2차원 배열 -> 1차원 배열

idx  = 3 * 1 + 1;

str = "123546789"

 

이런 방법을 통해 퍼즐의 모든 경우를 해쉬맵에 넣고 "1234567890"이 있는지 판단 후 출력하면 된다.

---

🌱 코드 및 풀이

	public class Main {
	public static HashMap<String, Integer> map = new HashMap<>();
	public static int[] dx = {0, 0, -1, 1};
	public static int[] dy = {-1, 1, 0, 0};
	public static void bfs(String input) {
	Queue<String> qu = new LinkedList<>();
	map.put(input, 0);
	qu.offer(input);
	while (!qu.isEmpty()) {
	String now = qu.poll();
	int zeroIdx = now.indexOf("0");
	// 1차원 배열 인덱스를
	// 3*3 2차원 배열 인덱스로 변환
	// ex. 1차원 배열 7번째 값은
	// 2차원 배열의 [2][1]자리에 존재한다.
	int nowX = zeroIdx % 3;
	int nowY = zeroIdx / 3;
	for (int i = 0; i < 4; i++) {
	int nx = nowX + dx[i];
	int ny = nowY + dy[i];
	if (nx < 0 || ny < 0 || nx >= 3 || ny >= 3) continue;
	// 2차원 배열의 인덱스를 -> 1차원 배열의 인덱스로 변환
	// 배열[2][1] 값은 -> 3*2+1 -> 배열[7]에 존재함
	int nextIdx = 3 * ny + nx;
	// StringBuilder의 메서드를 통해 0과 flag 자리 스왑
	StringBuilder sb = new StringBuilder(now);
	char flag = sb.charAt(nextIdx);
	sb.setCharAt(nextIdx, '0');
	sb.setCharAt(zeroIdx, flag);
	// 맵에 포함되지 않았다면 새로운 조합임 -> 방문체크 효과도있음(무한루프 방지)
	if (!map.containsKey(sb.toString())) {
	qu.offer(sb.toString());
	// 현재조합 과 (전번조합이 만들어 지기까지의 횟수 +1) 저장
	map.put(sb.toString(), map.get(now) + 1);
	}
	}
	}
	}
	public static void main(String[] args) throws IOException { //조건 입력
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st;
	String str = "";
	for (int i = 0; i < 3; i++) {
	st = new StringTokenizer(br.readLine(), " ");
	for (int j = 0; j < 3; j++) {
	str += st.nextToken();
	}
	}
	// 너비우선탐색으로 만들 수 있는 모든 경우의 조합을 만들고 맵에 저장한다.
	bfs(str);
	// 올바른 조합 "123456780"이 맵에 없다면, 만들 수 없는 경우임.
	if (map.containsKey("123456780")) {
	System.out.print(map.get("123456780"));
	} else {
	System.out.print(-1);
	}
	}
	}

view raw 퍼즐.java hosted with ❤ by GitHub

 

---

🌱 느낀 점

이 문제를 풀면서 이런 식으로도 문제를 접근할 수 있구나를 알게 되었고 기존에 못 풀던 문제를 위와 같은 아이디어와 접목하면

풀 수 있을 것 같다 특히 1차원 배열 인덱스를 2차원 배열인덱스로 변환해서 처리하는 부분이 가장 흥미로웠고

 

BFS의 방문처리도 해쉬맵으로도 할 수 있다는 것을 배워서 다른 문제에도 접목시켜서 내 것으로 만들어야겠다.