[Algorithm] 무식하게 풀기 (Brute-Force) #230201

본 게시글은 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 (구종만 저)"의 내용을 참고하여 기재하였습니다. 

 

[06] 무식하게 풀기 (Brute-Force)

재귀호출

재귀호출의 기저 사례 : 더 이상 쪼개지지 않는 마지막 조각에 도달했을 때 답을 반환하는 조건문을 작성하여야 함. 이 마지막 조각을 기저 사례라고 한다.

4중 for문을 통해 4가지 원소를 고르는 사례에서,

• 원소들의 총 개수
• 더 골라야 할 원소들의 개수
• 지금까지 고른 원소들의 번호

이 세가지를 함수의 인자로 넣어 재귀호출을 수행할 수 있다.

따라서 재귀호출로 완전탐색 문제를 풀 때는 아래의 프로세스를 사용한다.

(1) 문제의 분할
(2) 기저 사례의 선택
(3) 구현
(4) 시간복잡도 분석

문제1 : 소풍

#include <iostream>
using namespace std;

int n;
bool areFriends[10][10];

int countParings(bool taken[10]) {
    int firstFree = -1; // 가장 앞선 번호
    for (int i = 0; i < n; i++) {
        if (!taken[i]) { // 방문하지 않으면
            firstFree = i;  // 그 친구를 가장 앞선 번호로 선정
            break;
        }
    }

    // 기저사례 
    if (firstFree == -1) // 모두가 방문했으면
        return 1; // 재귀 종료

    // firstFree 학생과 짝지을 친구를 찾는다.
    int ret = 0;
    for(int pairWith = firstFree + 1; pairWith < n; pairWith++){
        if (!taken[pairWith] && areFriends[firstFree][pairWith]) {
            taken[firstFree] = taken[pairWith] = true;
            ret += countParings(taken); 
            taken[firstFree] = taken[pairWith] = false;
        }
    }
    return ret; 
}

새로 알게된 점

(1) 서로 친구라는 점을 이차원 배열로 지정한다. ⇒ 굳이 for문을 쓰지 않아도 두 친구가 서로 친구임을 알 수있다

(2) 제일 앞선 번호를 탐색할 때마다 찾아서 그 뒤의 번호와 비교하여 짝을 찾는다. ⇒ 앞, 뒤 중복되는 경우 제거

(3) 제일 앞선 번호를 구하는 과정에서 사용한 변수 firstFree를 사용해서 모두가 방문하였음을 동시에 체크

 

문제2 : 게임판 덮기

#include <iostream>
#include <vector>
using namespace std;

const int coverType[4][3][2] = {
    {{0,0}, {1, 0}, {0, 1}},
    {{0,0}, {0, 1}, {1, 1}},
    {{0,0}, {1, 0}, {1,1}},
    {{0,0}, {1,0}, {1, -1} }
};

bool set(vector<vector<int>>& board, int y, int x, int type, int delta) { // (y, x)를 type번 방법으로 덮거나, 덮었던 블록을 없앤다 
    bool ok = true;
    for (int i = 0; i < 3; i++) {
        const int ny = y + coverType[type][i][0];
        const int nx = x + coverType[type][i][1];
        if (ny < 0 || ny >= board.size() || nx < 0 || nx >= board[0].size()) // 판의 바깥에 있는경우
            ok = false;
        else if ((board[ny][nx] += delta) > 1) 
            ok = false;
    }
    return ok;
}

int cover(vector<vector<int>>& board) {
    int y = -1, x = -1; 
    // 처음 시작점을 찾는 부분
    for (int i = 0; i < board.size(); i++) {
        for (int j = 0; j < board[i].size(); j++) {
            if (board[i][j] == 0) { // 흰 칸 발견
                y = i;
                x = j;
                break;
            }
        }
        if (y != -1) // 흰 칸 발견
            break;
    }

    //  기저 사례1 : 모든 칸을 다 채웠으면 반환한다.
    if (y == -1)
        return 1;

    int ret = 0; 
    // 4가지 타입을 순환
    for (int type = 0; type < 4; type++) {
        // 블럭을 끼워넣으면서 ret 계산
        if (set(board, y, x, type, 1))
            ret += cover(board);

        // 다음 경우의 수 탐색을 위해 끼워넣은 블럭을 해체
        set(board, y, x, type, -1);
    }
    return ret;
}

핵심은 중복 제거, 왼쪽 위의 점부터 시작해서 차례로 쌓아가는 방식이다.

Target 점을 현재 남은 흰 칸에서 가장 왼쪽 위에 있는 칸부터 시작하므로 오른쪽, 아래쪽만 채우는 경우를 생각해서 Target 점을 기준으로 네가지 형태로 흰 칸을 채울 수 있다.

내가 놓친 부분!

(1) firstTarget을 생각한 부분은 좋았으나, 그 지점을 기준으로 덮을 수 있는 4가지 Type을 끌어내지 못함. 그리고 이 Type을 위와 같이 배열로 정의해야하는 필요성을 못느낌.

⇒ 문제 상황에 맞는 특정한 Type은 내가 배열로서 정의해줘야 한다.

(2) cover함수에서 이중 for문으로 처음 시작할 x, y 점을 찾는 시도는 완료, 그러나 블럭을 끼워넣고 해체하는 과정을 구현하지 못함.

(3) x와 y의 순서도 헷갈렸음. 테이블이 있으면 세로축이 y (전체 길이 h) 이고 가로축이 x (전체 길이 w)이므로, (y, x) 방식으로 값을 계산해야함.

ex) w = 2, h = 3 인 경우, 

(0, 0)	(0, 1)
(1, 0)	(1, 1)
(2, 0)	(2, 1)

(4) cover함수에서 if문으로 블럭 4가지 타입을 끼워넣어보고 “안되면” 다시 해체하는 방식을 떠올리지 못함.

set함수에서 nextX와 nextY가 (a) 판 밖으로 나가거나, (b) 겹치거나 (c) 검은 칸을 덮은 경우 false를 반환하도록 해서 위의 문제1 “쇼핑”에서 구현한 아래와 같은 방식을 정확하게 구현함

최적화 문제

가장 최적인 하나의 답을 내는 문제이다. 

예제) 여러 도시를 여행하기 위한 최단 경로를 계산하는 프로그램 (TSP)

• path 배열 : 현재 경로
• visited 배열 : 방문했는지 여부 저장
• currentLength 변수 : 지금까지 만든 경로의 길이

#include <iostream>
#include <vector>
#define MAX 100
#define INF 987654321;
using namespace std;

int n; // 도시의 수
double dist[MAX][MAX]; // X에서 Y까지의 거리 정보

double shortestPath(vector<int>& path, vector<int> visited, double currentLength) {
    // 기저 사례 
    // 모든 정점을 다 지나 원래로 돌아오는 경우
    if (path.size() == n)
        return currentLength + dist[path[0]][path.back()];
    // 지금까지의 경로 길이 + 처음으로 다시 돌아가는 비용

    double ret = INF;
    for (int next = 0; next < n; next++) {
        if (!visited[next]) continue; // 이미 방문한 노드면 생략
        int here = path.back(); // 현재 위치
        path.push_back(next);
        visited[next] = true;

        double cand = shortestPath(path, visited, currentLength + dist[here][next]);

        ret = min(ret, cand);
        visited[next] = false; 
        path.pop_back(); 
    }
    return ret; 
}

 

 

> 전체 코드 및 추가 설명

#include <iostream>
#include <vector>
#define MAX 8 // 요거 실수
#define INF 987654321;
using namespace std;

int n; // 도시의 수
double dist[MAX][MAX]; // X에서 Y까지의 거리 정보

double shortestPath(vector<int>& path, vector<bool> &visited, double currentLength) {
	// 기저 사례 
	// 모든 정점을 다 지나 원래로 돌아오는 경우
	if (path.size() == n)
		return currentLength + dist[path[0]][path.back()];
	// 지금까지의 경로 길이 + 처음으로 다시 돌아가는 비용

	double ret = INF;
	for (int next = 0; next < n; next++) {
		if (visited[next]) continue; // 이미 방문한 노드면 생략
		int here = path.back(); // 현재 위치
		path.push_back(next);
		visited[next] = true;
		
		double cand = shortestPath(path, visited, currentLength + dist[here][next]);

		ret = min(ret, cand);
		visited[next] = false; 
		path.pop_back(); 
	}
	return ret; 
}

int main() {
	int t; cin >> t; // 테스트 케이스
	for (int index = 0; index < t; index++) {
		cin >> n; // 도시의 수
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++){
				cin >> dist[i][j];
			}
		}

		double ways = INF;
		for (int j = 0; j < n; j++) {
			vector<int> path(1, j); // j로 초기화된 1개의 원소를 가지는 vector 생성
			vector<bool> visited(n, 0);
			visited[j] = true;

			ways = min(ways, shortestPath(path, visited, 0));
		}
		cout << ways << endl;
	}
	return 0; 
}

TSP 문제는 모든 노드에서 모든 노드로 갈 수 있기 때문에, main함수에서부터 for문을 돌려 모든 노드를 출발점으로 두고 시작한다. 0번 노드부터 시작한다고 가정해서 shortestPath(path, visited, 0)함수부터 진입하면,

(0) next = 0일때는 continue하고

(1) next = 1일때부터 코드가 돌아간다.

이 시점에서 shortestPath(path, visited, 0 + dist[0][1])이 호출되고, next = 0과 next = 1은 다시 continue된다. 그렇게 0 → 1 → 2의 경로를 돌아서 최종적으로 cand에는 dist[0] + dist[1]의 값이 담기게 된다. for문에서 shortestPath의 호출 종료 이후 ret은 cand의 값이 당연히 담기게 된다.

(2) next = 2 일 때,

shortestPath(path, visited, 0 + dist[0][2])이 호출되고, next = 0과 next = 2는 continue된다. 0→ 2→ 1의 경로로 cand에는 dist[0] + dist[2]의 값이 담기고, 호출 종료 이후 ret은 (1)에서 담은 값과 비교해서 더 작은 값이 담기게 되고, 최종적으로 리턴되어 main함수의 ways에 담기게 되는 것이다.

문제3 : 시계 맞추기

내가 푼 방식

#include <iostream>
#include <vector>
using namespace std;

const int INF = 9999, SWITCHES = 10, CLOCKS = 16; 
const char linked[SWITCHES][CLOCKS + 1] = {
    "xxx.............",
    "...x...x.x.x....",
    "....x.....x...xx",
    "x...xxxx........",
    "......xxx.x.x...",
    "x.x...........xx",
    "...x..........xx",
    "....xx.x......xx",
    ".xxxxx..........",
    "...xxx...x...x.." };

// 모든 시계가 12시 방향을 가리키고 있는지 여부 탐색
bool areAligned(const vector<int>& clocks) {
    for (int i = 0; i < CLOCKS; i++) {
        if (clocks[i] != 12)
            return false;
    }
    return true;
}

// swtch 번 스위치를 누른다. 
void push(vector<int>& clocks, int swtch) {
    for (int clock = 0; clock < CLOCKS; clock++) {
        if (linked[swtch][clock] == 'x') { // swtch와 clock이 연결되어있으면
            clocks[clock] += 3;
            if (clocks[clock] == 15)
                clocks[clock] = 3; 
        }
    }
}

int solve(vector<int>& clocks, int swtch) {
    // 마지막 스위치를 누르는 경우
    if (swtch == SWITCHES)
        return areAligned(clocks) ? 0 : INF;
    // 12시 방향으로 정렬되어 있으면 0을 반환, 그렇지 않으면 INF를 반환한다 

    // 현재 swtch를 0에서 3번 누르는 경우를 모두 검사하여 최솟값을 구한다.
    int ret = INF;
    for (int cnt = 0; cnt < 4; cnt++) {
        ret = min(ret, cnt + solve(clocks, swtch + 1));
        push(clocks, swtch);
    }

    return ret;
}

switch 하나를 누르는 횟수는 3번 이하로 제한되어있다. 4번 누르면 시계가 원점으로 돌아가게 되는데, 그럴 필요가 없기 때문이다. 따라서 0번 스위치부터 마지막 스위치까지 0~3번 누르는 경우를 모두 계산해서 가장 작은 값을 ret에 저장하면 된다. 그리고 areAligned 함수를 사용해서 마지막 스위치를 눌렀을 때 정렬이 되어있으면 최종적으로 0을 반환한다 . 그래야 해당 cnt의 값이 ret에 저장되기 때문이다.