Notice
Recent Posts
Recent Comments
Link
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
Archives
Today
Total
관리 메뉴

차근차근

[백준 1525] 퍼즐 본문

대학교/Algorithm

[백준 1525] 퍼즐

SWKo 2020. 3. 20. 01:40

0. 제목

  • 백준 1525 퍼즐
  • BOJ 1525 퍼즐
  • C++ 1525 퍼즐

1. 문제

https://www.acmicpc.net/problem/1525


2. 풀이

  • 이 문제는 브루트포스와 BFS를 사용하는 문제였다.
  • 아홉개의 칸 순서대로 이어지는 숫자로 표현할 것이기 때문에 0을 9로 바꿔주고 시작한다.
  • 정수를 입력받으면서 start라는 변수에 9자리 수를 저장한다.
  • key, value쌍을 가지고 있는 map을 사용하여 dist를 선언한다. dist[x]는 x까지 움직인 횟수를 뜻한다.
  • BFS를 사용하기 위해 큐를 선언하고 큐가 빌때까지 반복한다.
  • 큐의 맨 앞에 있는 정수를 문자열로 만들어준다. 그 후 pop을 하고 9가 저장되어 있는 인덱스를 찾는다.
  • 찾은 인덱스를 이용하여 x좌표와 y좌표를 찾는다.
  • 미로찾기와 비슷하게 상하좌우 범위를 확인하며 탐색한다.
  • 탐색 할때 상하좌우 교환을 해보고 한번도 가보지 않은 길이라면 큐에 push해준다. 또한, 그곳까지의 거리도 기존 거리에서 1을 추가해준다. 가지가 뻗어나가는 것을 생각하면 된다.
  • 그렇게 결국 큐가 비어서 반복문을 빠져 나오고 dist배열에서 123456789를 찾아본다. 만약 없다면, -1을 출력해주고 있다면 그곳까지 걸린 거리를 출력해준다.

3. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
 
int dx[4= {-1010};
int dy[4= {0-101};
 
int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int start = 0;
    int temp;
    
    //예시로 입력받은 것을 193425786처럼 만든다.
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            cin >> temp;
            if(temp == 0)
                temp = 9;
            
            start = start * 10 + temp;
        }
    }
    
    map<intint> dist; //key, value쌍
    queue<int> q;
    q.push(start);//193425786
    dist[start] = 0;//처음 위치까지 움직인 수는 0(초기값)
    
    while(!q.empty()){
        int now_num = q.front();//큐의 제일 앞 원소 저장
        string now_str = to_string(now_num);//문자열로 만들어줌
        q.pop();
        
        int z = (int)now_str.find('9');//9가 저장되어 있는 Index를 찾아줌
        int x = z / 3;//x좌표는 상하
        int y = z % 3;//y좌표는 좌우
        
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || nx > 2 || ny < 0 || ny > 2continue;//범위 벗어나면 continue
            string next_str = now_str;
            swap(next_str[x * 3 + y], next_str[nx * 3 + ny]);//교환
            int next_num = stoi(next_str);
            
            if(dist.count(next_num) == 0){//처음 가는 길이라면
                dist[next_num] = dist[now_num] + 1;//1추가
                q.push(next_num);
            }
        }
    }
    
    if(dist.count(123456789== 0)
        cout << "-1" << '\n';
    else
        cout << dist[123456789<< '\n';
 
    return 0;
}
 
 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 1987] 알파벳  (0) 2020.03.23
[백준 1759] 암호 만들기  (0) 2020.03.22
[백준 1697] 숨바꼭질  (0) 2020.03.19
[백준 10819] 차이를 최대로  (0) 2020.03.18
[백준 6378] 디지털 루트  (0) 2020.03.15
Comments