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

5 분 소요

블록이동하기 (프로그래머스 Level 3)

https://school.programmers.co.kr/learn/courses/30/lessons/60063

복잡하고 많은 구현을 요구하는 문제였다
일단 기본적으로는 BFS 문제에서 시작하지만
차이점이 2가지 있는데

드론의 크기가 2x1이다
드론은 90도로 회전이 가능하며 시간을 1초 사용
(추가적으로 드론은 4방향 이동이 가능하다)

개인적으로 푼 방법은
‘드론’을 - 의 형태와 | 형태로 나누어 구분하고
DP를 적용하여 이미 해당 모양의 드론이
더 적은 값으로 도착하여 있다면 해당 루트는 무시하는 것이였다
(나중에 보니 ‘해시 테이블’을 사용하여 방문 체크를 하는 방법도 있다고 한다)

가장 까다로웠던 것이
‘회전’인데
나는 드론의 좌측 혹은 위측을 x1,y1으로
우측 or 하측을 x2,y2로 나누어 생각하였다

이후, 해당 좌표와 드론 모양을 기준으로
가능한 8가지 ‘회전’을 체크하는 함수를 통하여 회전을 적용하였고
BFS를 돌렸다

4가지 방향에 대한 ‘이동’
상,하,좌,우 에 따라 queue에 집어넣음
모양에 따른 4가지 회전을 체크
역시 모양에 따른 4가지 회전을 queue에 집어넣음

구현 시간이 엄청나게 걸린 문제이다
dp를 사용하였기에 전반적으로 시간은 깔끔하게 나왔지만
세부적인 구현에 너무 시간을 잡아먹혔고
비슷한 코드를 복사하여 다르게 수정한 것으로
함수 이름이 rotate1,rotate2 … 이런식으로 짠 것도 존재한다
(네이밍을 신경 쓸 겨를이 없었지만)

그래도 개인적으로는 이러한 ‘board’ 유형에서
‘유닛’을 움직이는 문제에 약했던 것 같아 끝까지 도전해보았고
결국 통과하여 조금 뿌듯한 문제였다

Code

#include <vector>
#include<queue>
#include<limits.h>

using namespace std;

struct info
{
	// 좌측 혹은 상단
	int y1 = 0;
	int x1 = 0;

	// 우측 혹은 하단
	int y2 = 0;
	int x2 = 1;

	// 이동 시간
	int cost = 0;
};

bool isGoal(const vector<vector<int>>& board,const info& i)
{
	const int goal = board.size() - 1;
	if (i.x1 == goal &&
		i.y1 == goal)
		return true;

	if (i.x2 == goal &&
		i.y2 == goal)
		return true;

	return false;
}

bool isInBoard(const vector<vector<int>>& board, const info& i)
{
	const int n = board.size();

	if (i.x1 >= n ||
		i.x1 < 0 ||
		i.y1 < 0 ||
		i.y1 >= n)
		return false;

	if (i.x2 >= n ||
		i.x2 < 0 ||
		i.y2 < 0 ||
		i.y2 >= n)
		return false;

	return true;
}

bool isRotate(const vector<vector<int>>& board, info& i, bool isWide)
{
	const int n = board.size();

	if (i.x1 + 1 >= n ||
		i.x1 + 1 < 0 ||
		i.y1 + 1 < 0 ||
		i.y1 + 1 >= n)
		return false;

	// - 모양이라면
	if (isWide)
	{
		if (board[i.y1 + 1][i.x1] == 1 ||
			board[i.y1 + 1][i.x1 + 1] == 1)
			return false;

		i.x1 = i.x2;
		i.y1 = i.y2;

		i.y2 += 1;

		return true;
	}

	// | 모양이라면
	// x1,y1 녀석을 x1 + 1, y1 + 1으로 옮겨야 하는 상황
	//
	if (board[i.y1][i.x1 + 1] == 1 ||
		board[i.y1 + 1][i.x1 + 1] == 1)
		return false;

	i.x1 = i.x2;
	i.y1 = i.y2;

	i.x2 += 1;

	return true;
}

bool isRotate2(const vector<vector<int>>& board, info& i, bool isWide)
{
	const int n = board.size();

	// - 모양이라면
	if (isWide)
	{
		if (i.x1 + 1 >= n ||
			i.x1 + 1 < 0 ||
			i.y1 - 1 < 0 ||
			i.y1 - 1 >= n)
			return false;

		if (board[i.y1 - 1][i.x1] == 1 ||
			board[i.y1 - 1][i.x1 + 1] == 1)
			return false;

		i.x1 = i.x2;
		i.y1 = i.y2 - 1;

		return true;
	}

	if (i.x1 + 1 >= n ||
		i.x1 + 1 < 0 ||
		i.y1 + 1 < 0 ||
		i.y1 + 1 >= n)
		return false;

	// | 라면
	if (board[i.y1][i.x1 + 1] == 1 ||
		board[i.y1 + 1][i.x1 + 1] == 1)
		return false;

	i.x2 = i.x1 + 1;
	i.y2 = i.y1;

	return true;
}

bool isRotate3(const vector<vector<int>>& board, info& i, bool isWide)
{
	const int n = board.size();

	// - 모양이라면
	if (isWide)
	{
		if (i.x1 + 1 >= n ||
			i.x1 + 1 < 0 ||
			i.y1 - 1 < 0 ||
			i.y1 - 1 >= n)
			return false;

		if (board[i.y1 - 1][i.x1] == 1 ||
			board[i.y1 - 1][i.x1 + 1] == 1)
			return false;

		i.x2 = i.x1;
		i.y2 = i.y1;

		i.y1 -= 1;

		return true;
	}

	if (i.x1 - 1 >= n ||
		i.x1 - 1 < 0 ||
		i.y1 + 1 < 0 ||
		i.y1 + 1 >= n)
		return false;

	// | 라면
	if (board[i.y1][i.x1 - 1] == 1 ||
		board[i.y1 + 1][i.x1 - 1] == 1)
		return false;

	i.x1 -= 1;
	i.y1 = i.y2;

	return true;
}

bool isRotate4(const vector<vector<int>>& board, info& i, bool isWide)
{
	const int n = board.size();

	// - 모양이라면
	if (isWide)
	{
		if (i.x1 + 1 >= n ||
			i.x1 + 1 < 0 ||
			i.y1 + 1 < 0 ||
			i.y1 + 1 >= n)
			return false;

		if (board[i.y1 + 1][i.x1] == 1 ||
			board[i.y1 + 1][i.x1 + 1] == 1)
			return false;

		i.x2 = i.x1;
		i.y2 = i.y1 + 1;

		return true;
	}

	if (i.x1 - 1 >= n ||
		i.x1 - 1 < 0 ||
		i.y1 + 1 < 0 ||
		i.y1 + 1 >= n)
		return false;

	// | 라면
	if (board[i.y1][i.x1 - 1] == 1 ||
		board[i.y1 + 1][i.x1 - 1] == 1)
		return false;

	i.x2 = i.x1;
	i.y2 = i.y1;

	i.x1 -= 1;

	return true;
}

int solution(vector<vector<int>> board) {
	const int n = board.size();
	int answer = 0;
	queue<info> q;
	q.push(info());

	const int dx[4] = { 1,0, -1, 0 };
	const int dy[4] = { 0,1, 0, -1 };
	vector<vector<int>> dpWide(n,vector<int>(n,INT_MAX)); // - 모양 dp
	vector<vector<int>> dpSide(n,vector<int>(n,INT_MAX)); // | 모양 dp

	while (q.empty() == false)
	{
		auto now = q.front();
		q.pop();
		bool isWide = (now.x1 == now.x2) ? false: true; // 

		// 블럭이 좌표를 벗어난 경우이다
		if (isInBoard(board, now) == false)
		{
			continue;
		}

		// 이미 해당 모양이 now의 x1,y1에 해당하는 지점에 도착하였고 더 적은 값이다
		if (isWide)
		{
			if (dpWide[now.y1][now.x1] <= now.cost)
				continue;

			dpWide[now.y1][now.x1] = now.cost;
		}
		else
		{
			if (dpSide[now.y1][now.x1] <= now.cost)
				continue;

			dpSide[now.y1][now.x1] = now.cost;
		}

		if (isGoal(board, now))
		{
			answer = now.cost;
			break;
		}

		{
			// 그대로 진행
			for (int i = 0; i < 4; i++)
			{
				info next = { now.y1 + dy[i], now.x1 + dx[i],now.y2 + dy[i],now.x2 + dx[i],now.cost + 1 };

				if (isInBoard(board, next) == false)
					continue;

				// 블럭이 끼는 상황이다
				if (board[next.y1][next.x1] == 1 ||
					board[next.y2][next.x2] == 1)
					continue;

				q.push(next);
			}
		}

		{
			// | 모양이므로
			// -> 하여 모양 잡기
			// x2의 x1,x2를 바꾸어 주기
			info copyNow = now;
			if (isRotate(board, copyNow, isWide))
			{
				copyNow.cost += 1;
				q.push(copyNow);
			}

			copyNow = now;
			if (isRotate2(board, copyNow, isWide))
			{
				copyNow.cost += 1;
				q.push(copyNow);
			}

			copyNow = now;
			if (isRotate3(board, copyNow, isWide))
			{
				copyNow.cost += 1;
				q.push(copyNow);
			}

			copyNow = now;
			if (isRotate4(board, copyNow, isWide))
			{
				copyNow.cost += 1;
				q.push(copyNow);
			}
		}
	}

	return answer;
}

int main()
{
	// 7 (항상 목적지에 도달할 수 있도록 주어짐)
	solution({ {0, 0, 0, 1, 1},{0, 0, 0, 1, 0},{0, 1, 0, 1, 1},{1, 1, 0, 0, 1},{0, 0, 0, 0, 0} });
}

Twitter Facebook LinkedIn

Hyun JaeHoon

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

블록이동하기 (프로그래머스 Level 3)

Code

공유하기

댓글남기기

참고

Direct X InitDirect3D

Direct X Init 1

백준 Gold 5 A와 B

백준 Gold 4 동전 1