[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"이 있는지 판단 후 출력하면 된다.

---

🌱 코드 및 풀이

 

---

🌱 느낀 점

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

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

 

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