[Algorithm]Baekjoon 17070번 :: 파이프 옮기기 1

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

17070번: 파이프 옮기기 1

struct Node
{
    int y;
    int x;
    int type;
};
 
vector<vector<pair<int,int>>> dir = 
{ 
    {{0,1},{-1,-1}, {1,1}},
    {{-1,-1}, {1,0},{1,1}},
    {{0,1},{1,0},{1,1}}
};
 
int n = 0;
int arr[18][18] = { 0 };
bool check[18][18][3] = { 0 };
int result = 0;
 
void BFS()
{
    queue<Node> q;
    q.push({ 1,2,0 });
                                                                                  
    while (!q.empty())
    {
        Node curNode = q.front();
        q.pop();
 
        int curY = curNode.y;
        int curX = curNode.x;
        int curType = curNode.type;
 
        if (curY == n && curX == n)
        {
            result++;
            continue;
        }
 
        for (int i = 0; i < dir[curType].size(); i++)
        {
            if (dir[curType][i].first == -1) continue;
 
            int nextY = curY + dir[curType][i].first;
            int nextX = curX + dir[curType][i].second;
            
            if (arr[nextY][nextX] == 1) continue;
            if (i == 2)
            {
                if (arr[nextY - 1][nextX] == 1 || arr[nextY][nextX - 1] == 1) continue;
            }
 
            q.push({ nextY,nextX,i });
        }
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
 
    for (int i = 0; i < 18; i++)
    {
        for (int j = 0; j < 18; j++)
        {
            arr[i][j] = 1;
        }
    }
 
    cin >> n;
    
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> arr[i][j];
        }
    }
 
    BFS();
 
    cout << result;
}

문제 이해하자마자 그냥 BFS코드가 떠올라서 BFS로 짰는데 생각보다 성능이 안좋아서 다른 사람풀이를 봤더니 대체로 백트래킹으로 짰고.. 성능도 좀 더 좋았다.

뭐 위 코드도 통과는 되서 그냥 다른 문제로 넘어가도 되지만, 다른 유형으로도 푸는거에 많이 익숙해져야해서 백트래킹으로도 풀었다.

 

vector<vector<pair<int, int>>> dir =
{
    {{0,1},{-1,-1}, {1,1}},
    {{-1,-1}, {1,0},{1,1}},
    {{0,1},{1,0},{1,1}}
};
 
int n;
int result;
int arr[18][18];
 
 
void DFS(int sy, int sx, int type)
{
    if (sy == n && sx == n)
    {
        result++;
        return;
    }
 
    for (int i = 0; i < dir[type].size(); i++)
    {
        if (dir[type][i].first == -1) continue;
 
        int nextY = sy + dir[type][i].first;
        int nextX = sx + dir[type][i].second;
 
        if (arr[nextY][nextX] == 1) continue;
        if (i == 2)
        {
            if (arr[nextY - 1][nextX] == 1 || arr[nextY][nextX - 1] == 1) continue;
        }
 
        DFS(nextY, nextX, i);
    }
}
 
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
 
    for (int i = 0; i < 18; i++)
    {
        for (int j = 0; j < 18; j++)
        {
            arr[i][j] = 1;
        }
    }
 
    cin >> n;
    
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> arr[i][j];
        }
    }
 
    DFS(1, 2, 0);
 
    cout << result;
}

 

260ms가 BFS로 푼거고 108ms가 백트래킹으로 푼 문제다. 성능차이가 2배넘게 난다.