글 읽기 - bfs를 이용한 풀이에 대한 시간초과 문제 질문

sipsyong 5년 전 0

BFS를 이용하여 문제를 풀었습니다.

예를 들어

1 2 3

4 0 5

6 7 8 의 배열의 경우

======

1 0 3

4 2 5

6 7 8

----------

1 2 3

0 4 5

6 7 8

----------

1 2 3

4 5 0

6 7 8

----------

1 2 3

4 7 5

6 0 8

----------

과 같이 현재 0의 상하좌우 숫자를 바꾸는 방식으로 진행을 했습니다.

bfs를 위한 deque에는 각 배열을 숫자로 풀어서 int를 사용했습니다.

예시의 맨 위 배열의 경우 값이 123405678이 됩니다.

또, bfs를 순회하는 중에 중복된 배열의 접근을 방지하기 위해서

vector에 값을 집어넣고 find를 통해서 vector에 해당 값이 없는 경우에만 bfs를 진행하였습니다.

이렇게 되면 모든 가능한 배열의 조합인 경우의 수가 362,880 이라고 생각하고 코드를 실행했는데 속도가 너무 느립니다.

어느 부분에서 잘못이 있는지 어떻게 바꾸면 좋을지 조언 부탁드려도 될까요?

긴 질문글 읽어주셔서 감사합니다.

#include <iostream>
#include <deque>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct node
{
    int x;
    int cnt;
}Node;

int ccount = 0;

int main()
{
    int str[9];

    // 입력 받은 숫자 순서를 배열로 저장
    for (int i = 0; i < 9; i++)
    {
        cin >> str[i];
    }

    // 입력 받은 숫자를 순서대로 정수로 변환
    // ex> 
    // 1 2 3
    // 4 5 6
    // 7 8 0
    // ==> 123456780
    int result = 0;
    int ten = 100000000;
    for (int i = 0; i < 9; i++)
    {
        result += ten * str[i];
        ten = ten / 10;
    }

    // bfs를 위한 deque 선언
    deque<Node> dq;
    
    // 방문한 숫자 조합을 판단하기 위한 vector 선언
    vector<int> v;

    // 시작 숫자
    Node start = { result, 0 };


    v.push_back(result);
    dq.push_back(start);
    
    while (1)
    {
        // bfs가 비어 있으면 -1 출력 => 답이 없는 경우 -1 출력
        if (dq.empty())
        {
            cout << -1;
            break;
        }

        // 현재 노드를 deque에서 뽑아온다
        Node now = dq.front();
        dq.pop_front();

        // 뽑은 숫자가 정렬이 되어 있으면 123456780이면 bfs의 count 값을 출력
        if (now.x == 123456780)
        {
            printf("%d", now.cnt);
            break;
        }

        // 뽑은 숫자가 정렬이 되어 있지 않다면
        // 0을 상하좌우의 숫자와 바꾸는 BFS
        // 상하좌우 4방향이기 때문에 4개로 반복
        for (int i = 0; i < 4; i++)
        {
            
            int arr[9];
            int zeroX;
            int tempX = now.x;


            // 현재 정렬된 숫자에서 0을 찾기 편하게 하기 위해서
            // 숫자를 다시 배열로 바꾼다
            // ex
            // 123450786 를 
            //   
            //   
            // 1 2 3    배열로 바꾼다
            // 4 5 0
            // 7 8 6  
            for (int i = 8; i >= 0; i--)
            {
                arr[i] = tempX % 10;
                tempX = tempX / 10;
                if (arr[i] == 0)
                    zeroX = i;
            }


            // 상하좌우로 가능한 경우에 값을 바꾼다
            // 1 2 3
            // 4 5 0
            // 7 8 6
            // 을 위에 있는 수와 바꾸는 것으로 예를들면
            // 1 2 0
            // 4 5 3
            // 7 8 6
            // 으로 바꾸고 이 작업을 for 문 안에서 4번 반복한다.
            if (i == 0 && zeroX != 0 && zeroX != 1 && zeroX != 2)
            {
                int temp = arr[zeroX - 3];
                arr[zeroX - 3] = 0;
                arr[zeroX] = temp;
            }

            if (i == 1 && zeroX != 2 && zeroX != 5 && zeroX != 8)
            {
                int temp = arr[zeroX + 1];
                arr[zeroX + 1] = 0;
                arr[zeroX] = temp;
            }

            if (i == 2 && zeroX != 0 && zeroX != 3 && zeroX != 6)
            {
                int temp = arr[zeroX - 1];
                arr[zeroX - 1] = 0;
                arr[zeroX] = temp;
            }

            if (i == 3 && zeroX != 6 && zeroX != 7 && zeroX != 8)
            {
                int temp = arr[zeroX + 3];
                arr[zeroX + 3] = 0;
                arr[zeroX] = temp;
            }

            // 배열로 저장된 배열을 다시 정수로 변환
            int rresult = 0;
            int tten = 100000000;
            for (int i = 0; i < 9; i++)
            {
                rresult += tten * arr[i];
                tten = tten / 10;
            }


            // 정수를 vector에서 찾고 만약 없는 경우에만 bfs를 진행
            if (find(v.begin(), v.end(), rresult) == v.end())
            {
                Node next = { rresult, now.cnt + 1 };
                v.push_back(rresult);
                dq.push_back(next);
            }
        }
    }
 

}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

bfs를 이용한 풀이에 대한 시간초과 문제 질문

sipsyong 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말