1938번 통나무 옮기기

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

처음에 나의 접근은 방문처리를

3개(B,B,B)를 모두 하려 했지만, 생각해보니 굳이 이렇게 할 필요가 없었다.

즉, 중간만 방문처리 하면 된다.

또한, 가로, 세로 여부만 따지면 된다.

코드가 다소 긴 문제이다.

점 하나 하나 조건을 따져야하기 때문이다.

#include <bits/stdc++.h>
 
using namespace std;
 
struct info { int y1, x1, y2, x2, y3, x3, direct; };
 
vector<vector<char> > v;
 
pair<int, int> s[3], e[3];
 
queue<info> q;
 
bool visit[55][55][2];
 
int N;
 
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };
 
void rotate(int y1, int x1, int y2, int x2, int y3, int x3, int i)
{
    if (i == 0) // 가로에서 세로로 회전
    {
        if (0 <= y1 - 1 && y1 + 1 < N &&
            0 <= y2 - 1 && y2 + 1 < N &&
            0 <= y3 - 1 && y3 + 1 < N)
        {
            if (v[y1 - 1][x1] != '1' && v[y1 + 1][x1] != '1' &&
                v[y2 - 1][x2] != '1' && v[y2 + 1][x2] != '1' &&
                v[y3 - 1][x3] != '1' && v[y3 + 1][x3] != '1' &&
                !visit[y2][x2][1]
                )
            {    
 
                visit[y2][x2][1] = true;
                q.push({ y2 - 1, x2, y2, x2, y2 + 1, x2, 1 });
                
            }
        }
    }
    else if (i == 1) // 세로에서 가로로 회전
    {
        if (0 <= x1 - 1 && x1 + 1 < N &&
            0 <= x2 - 1 && x2 + 1 < N &&
            0 <= x3 - 1 && x3 + 1 < N)
        {
            if (v[y1][x1 - 1] != '1' && v[y1][x1 + 1] != '1' &&
                v[y2][x2 - 1] != '1' && v[y2][x2 + 1] != '1' &&
                v[y3][x3 - 1] != '1' && v[y3][x3 + 1] != '1' &&
                !visit[y2][x2][0]
                )
            {
                visit[y2][x2][0];
                q.push({ y2, x2 - 1, y2, x2, y2, x2 + 1, 0 });                    
            }
        }
    }
}
 
int bfs()
{
    int ret = 0;
 
    if (s[0].first == s[1].first && s[1].first == s[2].first)
    {
        q.push({ s[0].first, s[0].second, s[1].first, s[1].second, s[2].first, s[2].second, 0 });
    }
    else if (s[0].second == s[1].second && s[1].second == s[2].second)
    {
        q.push({ s[0].first, s[0].second, s[1].first, s[1].second, s[2].first, s[2].second, 1 });
    }
 
    while (!q.empty())
    {
        int qs = q.size();
 
        while (qs--)
        {
            int r1 = q.front().y1;
            int c1 = q.front().x1;
 
            int r2 = q.front().y2;
            int c2 = q.front().x2;
 
            int r3 = q.front().y3;
            int c3 = q.front().x3;
 
            int direct = q.front().direct;
 
            q.pop();
 
            if (r1 == e[0].first && c1 == e[0].second &&
                r2 == e[1].first && c2 == e[1].second &&
                r3 == e[2].first && c3 == e[2].second)
            {
                return ret;
            }
 
            rotate(r1, c1, r2, c2, r3, c3, direct);
 
            for (int i = 0; i < 4; i++)
            {
                int y1 = r1 + dy[i];
                int x1 = c1 + dx[i];
 
                int y2 = r2 + dy[i];
                int x2 = c2 + dx[i];
 
                int y3 = r3 + dy[i];
                int x3 = c3 + dx[i];
 
                if (y1 < 0 || y1 >= N ||
                    x1 < 0 || x1 >= N ||
                    y2 < 0 || y2 >= N ||
                    x2 < 0 || x2 >= N ||
                    y3 < 0 || y3 >= N ||
                    x3 < 0 || x3 >= N ||
                    v[y1][x1] == '1' || v[y2][x2] == '1' || v[y3][x3] == '1' ||
                    visit[y2][x2][direct]
                    ) continue;
 
                visit[y2][x2][direct] = true;
                q.push({ y1, x1, y2, x2, y3, x3, direct });
            }
        }
 
        ++ret;
    }
 
    return 0;
}
 
int main(void)
{
    int idx1 = 0, idx2 = 0;
 
    char c;
 
    cin >> N;
 
    for (int i = 0; i < N; i++)
    {            
        vector<char> input;
 
        for (int j = 0; j < N; j++)
        {
            cin >> c;
 
            if (c == 'B') s[idx1++] = { i, j };        
            else if (c == 'E') e[idx2++] = { i, j };
 
            input.push_back(c);
        }            
        
        v.push_back(input);
    }
 
    printf("%d\n", bfs());
 
    return 0;
}