[Programmers] 고고학 최고의 발견

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/131702?language=cpp

프로그래머스

 

백준 14927번 전구 끄기와 비슷한 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 첫 번째 행에 대해 모든 경우의 수를 구한 뒤

2. 두 번째 행부터 바로 위 행의 시곗바늘을 12로 만들도록 처리합니다.

3. 위와 같이 진행할 경우 1 ~ (N - 1)행의 시곗바늘은 모두 12를 바라보고 있습니다.

3.1 따라서 마지막 행의 시곗바늘이 모두 12를 바라보고 있을 경우 모든 시곗바늘이 12를 바라보고 있다고 판단할 수 있으며 이때 조작 횟수를 업데이트해 줍니다.

 

	#include <iostream>
	#include <vector>
	#include <cstring>
	using namespace std;
	const int INF = 987654321;
	typedef struct
	{
	int y, x;
	} Dir;
	Dir moveDir[5] = {{0, 0}, {1, 0}, {-1, 0}, {0, 1}, {0, -1}};
	int N;
	int result = INF;
	bool outOfBounds(int y, int x)
	{
	return y < 0 || y >= N || x < 0 || x >= N;
	}
	bool check(vector<vector<int>> &clockHands)
	{
	for (vector<int> clockHand : clockHands)
	{
	for (int hand : clockHand)
	{
	if (hand)
	{
	return false;
	}
	}
	}
	return true;
	}
	void rotate(int y, int x, int diff, vector<vector<int>> &clockHands)
	{
	for (int k = 0; k < 5; k++)
	{
	int nextY = y + moveDir[k].y;
	int nextX = x + moveDir[k].x;
	if (outOfBounds(nextY, nextX))
	{
	continue;
	}
	clockHands[nextY][nextX] = (clockHands[nextY][nextX] + 4 + diff) % 4;
	}
	}
	int getRotateCnt(vector<vector<int>> clockHands)
	{
	int result = 0;
	for (int y = 1; y < N; y++)
	{
	for (int x = 0; x < N; x++)
	{
	if (!clockHands[y - 1][x])
	{
	continue;
	}
	int diff = 4 - clockHands[y - 1][x];
	rotate(y, x, diff, clockHands);
	result += diff;
	}
	}
	if(!check(clockHands))
	{
	return -1;
	}
	return result;
	}
	void func(int x, int cnt, vector<vector<int>> &clockHands) {
	if (x == N)
	{
	int temp = getRotateCnt(clockHands);
	if (temp != -1)
	{
	result = min(result, temp + cnt);
	}
	return;
	}
	for (int diff = 0; diff < 4; diff++)
	{
	rotate(0, x, diff, clockHands);
	func(x + 1, cnt + diff, clockHands);
	rotate(0, x, -diff, clockHands);
	}
	}
	int solution(vector<vector<int>> clockHands) {
	N = clockHands.size();
	func(0, 0, clockHands);
	return result;
	}

view raw .cpp hosted with ❤ by GitHub

 

 

개발환경: Programmers IDE  

 

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