굳건하게

안녕하세요.

여행벌입니다.

오늘은 대표적인 백트래킹 문제 LOTTO 풀이를 해보겠습니다.

https://www.acmicpc.net/problem/6603

[알고리즘풀이]

1. 백트레킹기법을 이용하여 k개의 수를 고르면 출력을 반복해줍니다.

#include<cstdio>
#include<vector>

using namespace std;

int list[12];

void printPicked(vector<int>& picked) {
	for (int i = 0; i < 6; i++)
		printf("%d ", list[picked[i]]);
	printf("\n");
}

void pick(int ninput, vector<int>& picked, int toPick) {
	if (toPick == 0) {
		printPicked(picked);
		return;
	}
	int smallest = picked.empty() ? 0 : picked.back() + 1;
	for (int next = smallest; next < ninput; next++) {
		picked.push_back(next);
		pick(ninput, picked, toPick - 1);
		picked.pop_back();
	}
}

int main(void) {
	while(1){
		int ninput;
		scanf("%d", &ninput);

		if (ninput == 0) {
			return 0;
		}

		for (int i = 0; i < ninput; i++)
			scanf("%d", &list[i]);

		for (int i = 0; i <= ninput - 6; i++) {
			vector<int> picked;
			picked.push_back(i);
			pick(ninput, picked, 5);
			picked.pop_back();
		}
		printf("\n");
	}
}

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.

혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.

많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 

감사합니다.

안녕하세요.

여행벌입니다.

오늘은 백준 사이트 2668번 '숫자고르기' 문제를 다뤄보겠습니다.

정보올림피아드 초등부 문제로 DFS 탐색을 이용해서 구현할 수 있었습니다.

[알고리즘설계]

1. 입력된 정수를 list에 담고 앞에서부터 다음과 같이 탐색을 진행한다.

- 아직 방문하지않은 점이라면 Cycle이 형성되거나 이미 탐색한 점이 나올때까지 탐색을 진행한다.

 -> Cycle이 형성되었다면, Cycle의 크기만큼 Count 해주고, Cycle에 속한 숫자들을 Answer_list에 담아준다.

( Cycle의 형성 유무는 탐색을 하며 지나왔던 숫자와 다음에 가야할 숫자를 비교하며 판단한다. )

 -> 이미 탐색한 점이 나왔다면, 기존에 탐색한 루트이므로 종료한다.

2. 모든 점에 대한 탐색이 끝났다면, Answer_list를 Sort 한 후 앞에서부터 출력해준다.

[예시]

Index [ 1 2 3 4 5 6 7 ]

Input [ 3 1 1 5 5 4 6 ]

1 -> 3 -> 1 (Cycle 형성, 1,3을 Answer_list에 담아준다.)

2 -> 1 ( 1은 이미 방문한 점이므로 탐색을 종료한다. )

3 ( 1에서 탐색을 진행할 때 이미 방문한 점이므로 탐색을 종료한다. )

4 -> 5 -> 5 (Cycle 형성, 5를 Answer_list에 담아준다.)

5 ( 4에서 탐색을 진행할 때 이미 방문한 점이므로 탐색을 종료한다. )

6 -> 4 ( 4는 이미 방문한 점이므로 탐색을 종료한다. )

7 -> 6 ( 6은 이미 방문한 점이므로 탐색을 종료한다.

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

int answer[100], nanswer = 0;
int list[101];
bool check[101];
int check_circle(int, int, int[]);
void circle(int);

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
    
	int ninput;
	cin >> ninput;
	for (int i = 1; i <= ninput; i++)
		cin >> list[i];
        
	for (int i = 1; i <= ninput; i++) {
		if(check[i] == false) //방문하지않은점이라면 탐색 시작.
			circle(i);
	}
    
	cout << nanswer << '\n';
	sort(answer, answer + nanswer);
	for (int i = 0; i < nanswer; i++)
		cout << answer[i] << '\n';
}

int check_circle(int next, int count, int temp[]) {
	int i;
	for (i = count - 1; i >= 0; i--) {
		if (temp[i] == next) {
			return i;
		}
	}
	return -1;
}

void circle(int i) {
	int temp[100];
	int start = i;
	check[start] = true;
	int count = 0;
	temp[count++] = start;
	while (1) {
		int next = list[start];
		int ntemp = check_circle(next, count, temp);
		if (ntemp != -1) {
			for (int j = ntemp; j < count; j++) {
				answer[nanswer++] = temp[j];
			}
			return;
		}
        // 기존에 방문한 점이라면 종료.
		if (check[next] == true)
			return;
		start = next;
		check[start] = true;
		temp[count++] = start;
	}
}

초등부 문제라 입력은 작지만, 구현이 생각보다 까다로웠던 문제입니다. 

비슷한 문제로는 BOJ 9466번을 추천드립니다!

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.

혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.

많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 

감사합니다.

안녕하세요.

여행벌입니다.

오늘은 백준사이트의 14503번 '로봇청소기' 문제 풀이를 해보겠습니다.

[문제해석]

한글 문제라 따로 다루지 않겠습니다.

[알고리즘설계]

1. 시작 점부터 반시계 방향으로 돌며 청소를 안 한 곳이 있으면 청소를 해나간다.

(청소를 하지 않은 곳은 0, 벽은 1, 청소를 한 곳은 2를 저장해나가며 청소를 진행한다.)

2. 모든 방향을 돌았는데, 갈 곳이 없다면 후진을 한다.

- 후진을 할 수 있으면 후진 후 다시 1번부터 진행.

- 후진을 할 수 없다면(뒤가 벽이라면) 종료한다.

#include<iostream>

using namespace std;

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

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int row, column;
	cin >> row >> column;
	int x, y, dir;
	// dir 0 북 1 동 2 남 3 서
	cin >> x >> y >> dir;
	for (int i = 0; i < row; i++)
		for (int j = 0; j < column; j++)
			cin >> map[i][j];

	int count = 0;
	int flag = 1; // 조건을 만족하면 0으로 바꾸고 while을끝낸다.
	while (flag) {
		if (!map[x][y])
			count++;
		map[x][y] = 2;
		for (int i = 0; i < 5; i++) {
			if (i == 4) { // 4바퀴를 다 돌았는데도 for문이 안깨짐 -> 후진하거나 멈춰야됨.
				int next_x = x + dx[(dir + 3) % 4];
				int next_y = y + dy[(dir + 3) % 4];
				if (0 <= next_x && next_x < row && 0 <= next_y && next_y < column && map[next_x][next_y] != 1) {
					x = next_x;
					y = next_y;
				}
				else
					flag = 0;
                break;
			}
			int next_x = x + dx[dir];
			int next_y = y + dy[dir];
			dir = (dir + 3) % 4;
			if (0 <= next_x && next_x < row && 0 <= next_y && next_y < column && !map[next_x][next_y]) {
				x = next_x;
				y = next_y;
				break;
			}
		}
	}
	cout << count;
}

[중요코드]

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

// 뒤로 후진해야하는경우.
int next_x = x + dx[(dir + 3) % 4];
int next_y = y + dy[(dir + 3) % 4];

// 왼쪽으로 반시계방향으로 도는 경우
int next_x = x + dx[dir];
int next_y = y + dy[dir];
dir = (dir + 3) % 4;

0(북), 1(동), 2(남), 3(서) 를 의미하고 우리는 반시계 방향(왼쪽)으로 회전하면서 청소할 공간이 있는지 찾아볼 것이다.

또, 모든 방향에 청소할 공간이 없다면 뒤로 후진을 해야 한다.

따라서 dx, dy 배열을 다음과 같이 선언하고 next_x, next_y를 위와 같이 다루면 깔끔하게 탐색을 진행할 수 있다.

dx, dy 배열을 선언하고 next_x, next_y 변수를 다루는데 미숙해 생각보다 구현하는데 오래 걸렸다.

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.
혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.
많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 
감사합니다.