[백준 1525 C++] 퍼즐

오늘은 백준 1525 퍼즐에 대해 다뤄볼 예정이다.  

백준 1525번 문제는 BFS(Breadth First Search) 알고리즘을 사용하는 문제이다. 

퍼즐 문제 링크: https://www.acmicpc.net/problem/1525

1525번: 퍼즐

 

백준에 BFS 문제를 풀다보면 최단 경로를 구하는 문제가 주로 등장하곤 한다. 

그런데, 퍼즐 1525번 문제는 여태껏 풀었던 문제와는 조금 다른 문제 였던 것 같다. 

 

문제 설명

1	2	3
4	0	5
7	8	6

위와 같은 입력이 주어졌을 때,

1	2	3
4	5	6
7	8	0

최소한의 이동으로 위와 같이 만들어야한다. 

이걸 어떻게 BFS로 구현할 수 있을까? 

 

문제 풀이 

우선, 이 문제의 핵심은 어떤 방식으로 X, Y 좌표에 접근을 하는지 였던 것 같다. 

이제 본론으로 들어가, 문제를 어떻게 해결 하였는지 알아보도록 하자. 

 

2차원 배열을 사용하여 X, Y 간에 이동을 나타내는 것은 너무 불편하다는 생각이 들었다. 

그래서, 문자열을 사용하여 입력을 받아주었다. 

 

void Input() { 
	result = "123456780"; 
	int arr[3][3] ; 
	for (int i = 0 ; i < 3 ; i++) { 
		for (int j = 0 ; j < 3; j++) { 
			cin >> arr[i][j] ;  
			box += ('0' + arr[i][j]); 
		}
	}	
}

 

위 코드를 사용하여 입력을 받으면, 문제 설명에서 예시로 들었던 입력이 box에 "123405786" 문자열로 저장된다. 

위 방식으로 입력을 받은 후, 어떻게 좌표 X와 Y 값에 접근할 수 있을까? 

 

"123405786" 문자열을 보면, "123" 이 y 좌표가 0인 부분이고, '3' 은 x 좌표가 2인 부분이다. 

각 숫자의 좌표 값을 얻기 위해선, 아래와 같은 연산을 이용하면 된다. 

 

'0' 이 위치한 index 에서 / , % 연산을 통해 X 좌표, Y 좌표를 구할 수 있게 된다. 

X 좌표 = ('0'이 위치한 index) / 3 ; 

Y 좌표 = ('0'이 위치한 index) % 3; 

 

"123405786" ('0'이 위치한 index : 4) 

X 좌표 = 1 ; 

Y 좌표 = 1 ; 

 

이와 같이, 각 X, Y 좌표에 접근할 수 있게 된다. 

그럼, 접근 방식을 알았으니 BFS를 통해 "1234567890"을 만들어주면 될 것 같다. 

근데, 한 가지 걸리는 부분은 한 번 방문한 경우에는 더 이상 방문해서는 안되는데 이를 어떻게 해결할 수 있을까? 

 

이를 해결 하기 위해선, 각각의 경우를 문자열로 저장하여 특정 경우가 존재하는지 확인해주어야한다. 

이 때, set STL을 활용해주면 편리하게 위 부분을 해결할 수 있게 된다. 

set STL에 find 는 set 안에 존재하지 않을 경우 set.end() 를 반환하기 때문에 이를 활용하여 방문 했는지 확인해준다. 

 

위 내용을 토대로, 구현해주게 되면 아래 코드와 같이 구현할 수 있다.