https://www.acmicpc.net/problem/1525
1525번: 퍼즐
세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다.
www.acmicpc.net
처음에는 입력 받은 퍼즐을 하나씩 돌면서 빈 공간이 곁에 있는 노드와 빈 공간의 위치를 바꾸는 식으로 bfs를 구현하려고 했었다.
하지만 막상 구현하려고 보니
노드 자체가 3*3 2차원 배열인 만큼 메모리를 많이 써야 하는 것 아닐까 하는 생각도 들었고,
visited 배열을 어떻게 해야 할지도 몰랐고,
알고리즘 분류에 "해시를 사용한 집합과 맵" 이 있던데 어떻게 해시를 이용해서 구현하라는 거지 라는 생각도 들어서
문제에 손도 대지 못하고 있다가 그냥 풀이를 찾아봤다.
내가 놓쳤던 부분은
1. graph를 문자열로 받는 것
2. visited를 리스트가 아니라 딕셔너리로 구현하는 것
3. 빈 공간의 인덱스를 찾고 빈 공간의 주변 숫자와 자리를 바꾸도록 구현하는 것
.. 인 것 같다.
BFS에 대해 전보다는 많이 이해하고 있는 것 같기는 하지만, 여전히 조금만 꼬아놔도 못풀어서 슬프다😭
참고
1525번 풀이: https://fre2-dom.tistory.com/218
'코딩테스트 > 백준' 카테고리의 다른 글
| [백준] 5014번: 스타트링크 (0) | 2023.09.18 |
|---|---|
| [백준] 2186번: 문자판 (0) | 2023.09.17 |
| [백준] 1697번: 숨바꼭질 (0) | 2023.09.16 |
| [백준] 2251번: 물통 (0) | 2023.09.16 |
| [백준] 1963번: 소수 경로 (0) | 2023.09.13 |