백준 1938번 통나무 옮기기 - C++ 풀이

---

 

1. 통나무의 위치와 방향 값으로 평지의 상태를 나타낼 수 있다.
2. 평지의 상태를 그래프의 노드로 생각하고, 한 번의 연산으로 도달 가능한 상태들을 모두 간선으로 잇는다.
3. 초기 상태 노드에서 도착 상태 노드로 가는 최단거리를 BFS를 사용하여 구한다.

 

1. 통나무의 위치와 방향 값으로 평지의 상태를 나타낼 수 있다.

 평지에서 움직이는 것은 통나무뿐이다. 따라서 평지의 상태를 나타내기 위해 필요한 값은 통나무의 위치와 놓인 방향뿐이다.

 

2. 평지의 상태를 그래프의 노드로 생각하고, 한번의 연산으로 도달 가능한 상태들을 모두 간선으로 잇는다.

 통나무의 위치와 방향을 가지고 평지의 상태를 나타낸다. 그리고 하나의 상태를 그래프 상의 하나의 노드로 생각해준다. 그리고 한 번의 연산으로 도달 가능한 상태들끼리 간선으로 이어준다.

 

3. 초기 상태 노드에서 도착 상태 노드로 가는 최단거리를 BFS를 사용하여 구한다.

 그래프에서 하나의 간선은 한번의 연산을 의미하므로, 초기 상태 노드에서 도착 상태 노드로 가는 최단 거리가 곧 최소 연산 횟수가 된다.

반응형

---

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

const int H = 0, V = 1;
const int UP = 0, DOWN = 1, LEFT = 2, RIGHT = 3, TURN = 4;

int N;
char board[50][50];
bool visit[50][50][2];

struct Log {
    int r, c, d;
    
    bool operator ==(Log& l) {
        return r == l.r && c == l.c && d == l.d;
    }
    
    vector<Log> wholeLogs() {
        vector<Log> ret;
        
        int dr[2][3] = {{0, 0, 0}, {-1, 0, 1}};
        int dc[2][3] = {{-1, 0, 1}, {0, 0, 0}};
        
        for (int i=0; i<3; i++) {
            ret.push_back({r+dr[d][i], c+dc[d][i]});
        }
        
        return ret;
    }
    
    Log moved(int direction) {
        int dr[] = {-1, 1, 0, 0};
        int dc[] = {0, 0, -1, 1};
        
        if (direction == TURN) return {r, c, 1-d};
        else return {r+dr[direction], c+dc[direction], d};
    }
    
    bool canMove(int direction) {
        if (direction != TURN) {
            Log movedLog = moved(direction);
            vector<Log> movedLogs = movedLog.wholeLogs();
            
            for (auto l: movedLogs) {
                if (l.r < 0 || l.r >= N || l.c < 0 || l.c >= N) return false;
                if (board[l.r][l.c] == '1') return false;
            }
        }
        else {
            for (int i=-1; i<=1; i++) {
                for (int j=-1; j<=1; j++) {
                    int nr = r+i;
                    int nc = c+j;
                    if (nr < 0 || nr >= N || nc < 0 || nc >= N) return false;
                    if (board[nr][nc] == '1') return false;
                }
            }
        }
        
        return true;
    }
};

int BFS(Log s, Log e) {
    queue<pair<int, Log>> q;
    
    q.push({0, s});
    visit[s.r][s.c][s.d] = true;
    
    while (!q.empty()) {
        int dist = q.front().first;
        Log curr = q.front().second;
        q.pop();
        
        if (curr == e) return dist;
        
        for (int i=0; i<5; i++) {
            Log next = curr.moved(i);
            
            if (visit[next.r][next.c][next.d]) continue;
            if (!curr.canMove(i)) continue;
            
            visit[next.r][next.c][next.d] = true;
            q.push({dist+1, next});
        }
    }
    
    return 0;
}

Log findMiddleLog(vector<pair<int, int>> v) {
    sort(v.begin(), v.end());
    
    int r = v[1].first;
    int c = v[1].second;
    int d = v[0].first == v[1].first ? H : V;
    
    return {r, c, d};
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    vector<pair<int, int>> s, e;
    
    cin >> N;
    for (int i=0; i<N; i++) {
        string temp;
        cin >> temp;
        
        for (int j=0; j<N; j++) {
            board[i][j] = temp[j];
            
            if (board[i][j] == 'B') s.push_back({i, j});
            else if (board[i][j] == 'E') e.push_back({i, j});
        }
    }
    
    cout << BFS(findMiddleLog(s), findMiddleLog(e));

    return 0;
}