백준 1525. 퍼즐 [실패]

1.실패 원인

완탐 + 그래프 문제는 최대한 접근하고 남의 풀이를 보고 이해하는 걸로 만족해야할듯 하다. 제대로 맞춘 문제가 진짜 단순 완탐문제 한 문제 정도라니ㅜㅜ..

 

일단 다른 코드들을 보니 백준님의 풀이가 있었던 모양이다. 이런 방식으로 생각해서 할 수 있는 사람이 몇이나 될까 궁금하다. 당연히 좌표문제고 bfs라 2차원 배열을 사용하였는데.. 정수형태로 만들어서 앞서 포스팅 된 bfs 목표 숫자까지의 최소경로 문제로 푼다는 것은 감히 생각할 수도 없었다. 

 

좌표 문제라서 dx,dy 배열을 사용하는 점을 다시 상기할 수 있어서 좋았고 2차원 배열을 string 형태로 만든후 사칙 연산으로 2차원 배열 좌표를 찾아내듯 할 수 있다는 것도 신박했다('/' , '%' 연산). 아무튼간에.. 이 문제는 아직 내가 모르는 기술들이 많다는 것을 깨닫게 해준 문제이다.

 

2.작성 코드

#include <iostream>
#include <string>
#include <map>
#include <queue>

using namespace std;

int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n = 3;
    int start = 0;

    // 2차원 배열이 아닌 하나의 정수로 나타낸다. (0을 9로 입력해서)
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<n; j++) {
            int temp;
            cin >> temp;
            if (temp == 0) {
                temp = 9;
            }
            start = start * 10 + temp;
        }
    }

    map<int, int> dist;
    queue<int> q;
    q.push(start);
    dist[start] = 0;

    while (!q.empty())
    {
        int now_num = q.front();
        string now = to_string(now_num);
        q.pop();

        int z = now.find('9');
        int x = z / 3;
        int y = z % 3;

        for (int k = 0; k < 4; k++)
        {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx >= 0 && nx < n && ny >= 0 && ny < n)
            {
                string next = now;
                swap(next[x * 3 + y], next[nx * 3 + ny]);
                int num = stoi(next);

                if (dist.count(num) == 0)
                {
                    dist[num] = dist[now_num] + 1;
                    q.push(num);
                }
            }
        }
    }

    // dist[123456789] : 2차원 배열이 123 / 456 / 780 으로 완성됐다는 의미.
    if (dist.count(123456789) == 0)
        cout << "-1" << "\n";
    else
        cout << dist[123456789] << "\n";

    return 0;
}

3.참고 코드

https://wjdgus2951.tistory.com/73

[백준] 1525번 퍼즐

 

4. 해결 방안

사실 정말 막막하다. 외운다 한들 응용이 불가능한 영역이 아닌가? 수학 문제 풀듯이 문제를 파악하고 어떤 유형인지 생각하고 무슨 식을 써서 중간 답들을 도출해내고 궁극적으로 답을 써내는게 가능한지 의문이다. 지금 이 문제는 '무슨 식을 써서' 부분에서 감히 생각할 수도 없는 엄청난 거리감을 느끼게 해주는듯 하다. 0을 9로 바꾼다던가.. 2차원 배열을 string으로 생각한다던가 하는 것은.. 말 그대로 '그렇게 해보면 되지 않나?' 정도의 추상적인 과정이 아닌가.. '이러이러한 문제들은 이러이러한 방식으로 접근해서 이러이러한 기법들이 주축이되어 답이 도출된다.' 와 같은 방식이 아닌 이상 솔직히 알고리즘 공부를 한다한들 의미가 없을듯 하다.