[백준/C++] 1525. 퍼즐

문제

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

 

풀이

BFS를 이용해서 풀었다.

그리고 구조체를 만들어, 큐에 구조체를 넣는 방식으로 BFS를 구현했다.

 

첫 번째 시도

방문체크를 876543211 크기의 배열 이용

구조체 안에 int 3개(r, c, count), 3x3 vector 한 개

 

→ 메모리 초과 !

 

두 번째 시도

구조체에 너무 많은 것들이 들어있는게 문제인가 싶어서, 구조체안에 int 1개, string 1개만 넣도록 했다.

 

→ 메모리 초과 ! 

 

최종 시도 

방문 체크를 string set을 이용해서 했다. 876543211크기의 visited 배열을 만든 것 자체가 메모리 초과의 원인인 것 같았다. 

 

 

코드

#include <iostream>
#include <queue>
#include <vector> 
#include <string> 
#include <set>

using namespace std;

set<string> visited;

int dr[4] = {-1,1,0,0};
int dc[4] = {0,0,-1,1};
string mapToString(vector<vector<int>> map) {
    string s = "";
    for (int r = 0;r < 3;r++) {
		for (int c = 0;c < 3;c++) {
			s += (char)(map[r][c]+'0');
		}
	}
    return s;
}
struct Node {
    int count;
    string table;
};

string answer = "123456780";
int BFS(int start_r, int start_c, vector<vector<int>> map) {
    queue<Node> q;
    string table = mapToString(map);
    q.push({0, table});
    visited.insert(table);

    if(answer == table)
        return 0;
    while (!q.empty()) {
        string table = q.front().table;
        int count = q.front().count;
        int nowIdx = table.find('0');
        int r = nowIdx/3;
        int c = nowIdx-r*3;
        q.pop();
        for (int i=0;i<4;i++){
            int next_r = r + dr[i];
            int next_c = c + dc[i];
            if (next_r < 0 || next_r > 2 || next_c < 0 || next_c > 2) continue;
            int nextIdx = next_r*3+next_c;
            table[nowIdx] = table[nextIdx];
            table[nextIdx] = '0';
            int num = stoi(table,nullptr);
            if (visited.find(table) == visited.end()){
                if (answer == table)
                    return count+1;
                q.push({count+1, table});
                visited.insert(table);
            }
            // 원상복구 
            table[nextIdx] = table[nowIdx];
            table[nowIdx] = '0';
        }
    }
    return -1;
}

int main(void) {
	int R, C;
    vector<vector<int>> map(3, vector<int>(3,0));
	for (int r = 0;r < 3;r++) {
		for (int c = 0;c < 3;c++) {
            int input;
			cin >> input;
            map[r][c] = input;
			if (map[r][c] == 0) {
				R = r;C = c;
			}
		}
	}
	int result = BFS(R, C, map);
    cout << result << endl;
	return 0;
}

 

결과