[백준] 1525 퍼즐 C++

1. 문제 설명

• 링크 : https://www.acmicpc.net/problem/1525

 

 

---

2. 풀이 과정

• 문제 해결의 흐름
  1.  문자열의 형태로 입력 받는다. ex) "1034567"
  2.  이차원 배열을 bfs를 통해 탐색한다. (queue에 push되는 값 : 0의 위치값과 퍼즐 위치 정보를 담은 문자열) 
  3.  퍼즐을 이동시킨 형태 자체가 갱신값이므로 문자열로 치환하여 방문 처리해주자.
     • 이동하여 특정 위치에 도달하는 문제 : 이동 위치가 갱신 값
     • 연산하여 특정 값을 만드는 문제 : 연산 결과가 갱신 값
  4.  방문처리되는 문자열의 정수값은 1억이다. 그렇기에 int형 배열에 2억 개의 값을 초기화시킨다면 메모리 초과가 발생하므로 해시맵을 사용하였다.

 

• 나의 코드 

#include <iostream>
#include <queue>
#include <unordered_map> // 해시맵 사용

using namespace std;

int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

struct r_c_string { // queue에 저장할 변수의 데이터 타입 지정
    int row;
    int col;
    string str;
};

string answer_str = "123456780"; // 정답이 되는 문자열
unordered_map<string, int> visited; // int 배열은 메모리 초과,, 그래서 해시맵으로 변경

queue<r_c_string> q;



int bfs() {
    visited[q.front().str] = 1; // 처음 위치 방문 처리

    while(!q.empty()) {
        // 현재 행, 열 위치 및 문자열, 그리고 0의 위치
        int cur_r = q.front().row;
        int cur_c = q.front().col;
        string cur_str = q.front().str;
        int zero_position = cur_str.find('0'); // cur_str에서 0의 위치
        q.pop();

        // 반환 조건
        if (cur_str == answer_str) return visited[cur_str] - 1;

        // cur_str를 이차원 int형 배열로 바꾼 뒤 상하좌우 탐색해야 함
        int cur_arr[3][3] = {};
        int index = 0;
        for (int r = 0; r < 3; r++) {
            for (int c = 0; c < 3; c++) {
                cur_arr[r][c] = cur_str[index] - '0';
                index += 1;
            }
        }

        // 상하좌우 탐색
        for (int i = 0; i < 4; i++) {
            int next_r = cur_r + dr[i];
            int next_c = cur_c + dc[i];

            // 범위를 벗어나면 continue
            if (next_r < 0 || next_r > 2 || next_c < 0 || next_c > 2) continue;

            // 0의 위치와 next_val의 위치를 바꿔준다.
            string next_str = cur_str;
            int next_position = next_str.find(cur_arr[next_r][next_c] + '0');
            char tmp = next_str[zero_position];
            next_str[zero_position] = next_str[next_position];
            next_str[next_position] = tmp;

            // 첫 방문이라면 queue에 push!!
            if (visited[next_str] == 0) {
                r_c_string next_val;
                next_val.row = next_r;
                next_val.col = next_c;
                next_val.str = next_str;
                q.push(next_val);
                visited[next_str] = visited[cur_str] + 1;
            }
        }
    }

    return -1;
}




int main() {
    // 입력 받기
    r_c_string first_val;
    for (int r = 0; r < 3; r++) {
        for (int c = 0; c < 3; c++) {
            int val;
            cin >> val;
            first_val.str += to_string(val); // 입력 받은 숫자를 문자열로 변환하여 전체 문자열에 결합

            if (val == 0) { // 처음 0의 위치
                first_val.row = r;
                first_val.col = c;
            }
        }
    }
    q.push(first_val);

    cout << bfs(); // 결과 출력

    return 0;
}

 

• 이 문제를 통해 얻어갈 수 있는 것들
  • ⭐️⭐️⭐️ 해시맵 unordered_map 
    • ⭐️ 해쉬테이블로 구현한 자료구조로 탐색 시간복잡도는 O(1)이다.
    • map보다 빠른 탐색을 하기 위한 자료구조
    • ⭐️ 중복된 데이터를 허용하지 않는다.
    • unordered_map<string, int> um;로 선언한 경우 um["apple"] = 3;와 같이 값을 대입할 수 있다. 
    • .size() 메서드를 통해 맵의 크기를 확인할 수 있다.
    • .find(key) 메서드를 통해 맵에서 key에 해당하는 원소의 위치 인덱스를 찾을 수 있다.
    • .count(key) 메서드를 토앻 맵에서 key에 해당하는 원소의 갯수를 찾을 수 있다.
  • ⭐️ int to string : to_string('int value') 메서드를 통해 구현 가능
  • ⭐️ char to int : 'char value' - '0'
  • ⭐️ int to char : 'int value' + '0' 

---

3. 후기 

해시맵의 사용법을 제대로 알아간다.