프로그래머스 - 블록 이동하기

문제 링크입니다 : programmers.co.kr/learn/courses/30/lessons/60063

코딩테스트 연습 - 블록 이동하기

 

알고리즘 자체는 BFS로 굉장히 쉽다.

 

하지만 구현이 상당히 어렵기 때문에 시간이 꽤 오래 걸렸다...

 

실수를 줄인다면 시간을 3분의 1 이하로 줄일 수 있을 거 같은데... 실수를 줄이는 연습부터 해야겠다.

 

그림을 그리면서 하니까 실수가 조금 줄어드는 것 같다. 그림을 그리면서 실수를 줄이자.

 

 

 

 

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

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


// 짝수 위, 홀수 아래
const int dy2[4] = {-1, 0, -1, 0};
const int dx2[4] = {0, 0, 1, 1};


// 짝수 왼쪽, 홀수 오른쪽
const int dy3[4] = {0, 0, 1, 1};
const int dx3[4] = {-1, 0, -1, 0};


int n;
vector<vector<vector<bool>>> visited;

bool isClear(vector<vector<int>>& board, int y, int x) {
    if(y < 0 || y + 1 >= n || x < 0 || x + 1 >= n) return false;
    for(int i = 0; i < 2; i++) {
        for(int j = 0; j < 2; j++) {
            if(board[y + i][x + j]) return false;
        }
    }
    return true;
}

int bfs(vector<vector<int>>& board) {
    // {{y, x}, isVer}
    queue<pair<pair<int, int>, bool>> q;
    q.push({{0, 0}, 0});
    visited[0][0][0] = true;
    
    int ret = 0;
    
    while(!q.empty()) {
        int qSize = q.size();
        // cout << "qSize : " << qSize << endl;
        for(int i = 0; i < qSize; i++) {
            int cy = q.front().first.first;
            int cx = q.front().first.second;
            bool cver = q.front().second;
            q.pop();
            
            // cout << cy << ' ' << cx << ' ' << cver << " -- " << ret << endl;
            
            if(cver) {
                if(cy == n - 2 && cx == n - 1) return ret;
            } else {
                if(cy == n - 1 && cx == n - 2) return ret;
            }
            
            
            for(int dir = 0; dir < 4; dir++) {
                int ny = cy + dy[dir];
                int nx = cx + dx[dir];
                if(cver) {
                    if(ny < 0 || ny + 1 >= n || nx < 0 || nx >= n) continue;
                    if(board[ny][nx] || board[ny + 1][nx]) continue;
                } else {
                    if(ny < 0 || ny >= n || nx < 0 || nx + 1 >= n) continue;
                    if(board[ny][nx] || board[ny][nx + 1]) continue;
                }
                if(visited[ny][nx][cver]) continue;
                visited[ny][nx][cver] = true;
                q.push({{ny, nx}, cver});
            }
            
            if(cver) {
                
                // 짝수는 위, 홀수는 아래
                for(int dir = 0; dir < 4; dir++) {
                    int ny = cy + dy3[dir];
                    int nx = cx + dx3[dir];
                    if(dir <= 1) {
                        if(!isClear(board, ny, nx)) continue;
                    } else {
                        if(!isClear(board, ny - 1, nx)) continue;
                    }
                    if(visited[ny][nx][!cver]) continue;
                    visited[ny][nx][!cver] = true;
                    q.push({{ny, nx}, !cver});
                }
                
            } else {
                // 짝수는 위, 홀수는 아래
                for(int dir = 0; dir < 4; dir++) {
                int ny = cy + dy2[dir];
                int nx = cx + dx2[dir];
                if(dir <= 1) {
                    if(!isClear(board, ny, nx)) continue;
                } else {
                    if(!isClear(board, ny, nx - 1)) continue;
                }
                
                if(visited[ny][nx][!cver]) continue;
                visited[ny][nx][!cver] = true;
                q.push({{ny, nx}, !cver});
                }
            }
        }
        ret++;
    }
    
    
    return -1;
}


int solution(vector<vector<int>> board) {
    int answer = 0;
    n = board.size();
    
    visited.assign(n, vector<vector<bool>>(n, vector<bool>(2, false)));
    
    answer = bfs(board);
    
    return answer;
}

 

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~