알못에서 잘알까지

    10번 문제   

programmers.co.kr/learn/courses/30/lessons/43165

    내가 풀이한 답   

 더하는 경우와 빼는 경우만 고려하면 되므로 재귀 함수를 2번 호출하여 구하면 쉽게 구할 수 있다.

#include <string>
#include <vector>
#include <iostream>
using namespace std;
int answer = 0;

void dfs(int level, int sum, vector<int> numbers, int target){
    if(level == numbers.size()){
        if(target==sum) {
            answer++;
        }
    }
    else {
        dfs(level+1, sum+numbers[level], numbers, target);
        dfs(level+1, sum-numbers[level], numbers, target);
    }
}

int solution(vector<int> numbers, int target) {
    
    dfs(0, 0, numbers, target);
    
    return answer;
}

    9번 문제   

    내가 풀이한 답   

 7, 8번 문제와 비슷한 유형을 계속 풀다보니 재귀함수를 몇 번 써야 하는지가 중요하게 느껴졌다.  7번과 8번은 포함o, 포함 x로 2가지의 경우만 고려하면 됐지만 위 문제 같은 경우는 +, -, 포함x 총 3가지의 경우를 고려해야 한다. 

//#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int n, m, a[11], count = 0;

void dfs(int level, int sum){
	if(level == n+1){
		if(m == sum) count++;
	}
	else {
		dfs(level+1, sum+a[level]);
		dfs(level+1, sum-a[level]);
		dfs(level+1, sum);
	}
}
	
int main() {
	//freopen("input.txt", "rt", stdin);
	int i;
	cin >> n >> m;
	for(i=1; i<=n; i++){
		cin >> a[i];
	}
	
	dfs(1, 0);
	
	if(count!=0) cout << count;
	else cout << -1; 
			
	return 0;
}

    사이트의 답안   

#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
int a[11], n, m, cnt=0;
void DFS(int L, int sum){
	if(L==n+1){
		if(sum==m){
			cnt++;
		}
	}
	else{
		DFS(L+1, sum+a[L]);
		DFS(L+1, sum);
		DFS(L+1, sum-a[L]);
	}
}

int main(){
	freopen("input.txt", "rt", stdin);
	int i;
	scanf("%d %d", &n, &m);
	for(i=1; i<=n; i++){
		scanf("%d", &a[i]);
	}
	DFS(1, 0);
	if(cnt==0) printf("-1\n");
	else printf("%d\n", cnt);
	return 0;
}

    8번 문제   

    내가 풀이한 답   

 앞의 7번 문제를 응용하면 쉽게 풀 수 있다. 

 두 개의 부분집합으로 나뉘기 때문에 부분집합의 총 합과 (전체 총 합 - 부분집합의 총 합)이 같으면 두 부분 집합이 같게 된 점을 이용하면 쉽게 풀 수 있다.

//#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int n, a[11], total=0;
bool flag = false;

void dfs(int level, int sum){
	if(level == n+1){
		if(total-sum == sum) flag = true; 
	}
	else {
		dfs(level+1, sum+a[level]);
		dfs(level+1, sum);
	}
}

int main() {
	//freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	
	int i;
	cin >> n;
	for(i=1; i<=n; i++){
		cin >> a[i];
		total+=a[i];
	}
	
	dfs(1, 0);
	
	if(flag) cout << "YES";
	else cout << "NO";
	
	return 0;
}

    사이트의 답안   

#include<stdio.h>
int n, a[11], total=0;
bool flag=false;
void DFS(int L, int sum){
	if(sum>(total/2)) return;
	if(flag==true) return;
	if(L==n+1){
		if(sum==(total-sum)){
			flag=true;
		}		
	}
	else{
		DFS(L+1, sum+a[L]);
		DFS(L+1, sum);
	}
}
int main(){
	freopen("input.txt", "rt", stdin);
	int i;
	scanf("%d", &n);
	for(i=1; i<=n; i++){
		scanf("%d", &a[i]);
		total+=a[i];
	}
	DFS(1, 0);
	if(flag) printf("YES\n");
	else printf("NO\n");
	return 0;
}

    7번 문제   

    내가 풀이한 답   

 위의 그림과 같이 완전탐색으로 n 값에 대한 부분집합을 구할 수 있다. 해당 숫자를 포함하는 경우와 포함하지 않는 경우를 나누면 해결할 수 있다.  

//#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int n, check[11];

void dfs(int level){
	if(level==n+1){
		for(int i=1; i<=n; i++){
			if(check[i]==1) cout << i << " ";
		}
		cout << endl;
	}
	else {
		check[level] = 1;
		dfs(level+1);
		check[level] = 0;
		dfs(level+1);
	}
}

int main() {
	//freopen("input.txt", "rt", stdin);
	cin >> n;
	
	dfs(1);
	return 0;
}

    사이트의 답안   

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int n, ch[100];
void DFS(int L){
	int i;
	if(L==n+1){
		for(i=1; i<=n; i++){
			if(ch[i]==1) printf("%d ", i);
		}
		puts("");
	}
	else{
		ch[L]=1;
		DFS(L+1);
		ch[L]=0;
		DFS(L+1);
	}
}	
int main(){
	freopen("input.txt", "rt", stdin);
	scanf("%d", &n);
	DFS(1);
	return 0;
}

    6번 문제   

    내가 풀이한 답   

• 전위순회(Preorder): 부모노드를 먼저 방문하고 자식 노드를 방문
• 중위순회(Inorder): 왼쪽 자식을 먼저 방문하고 부모노드를 방문
• 후위순회(Postorder): 자식 노드를 먼저 방문하고 부모노드를 방문

 위의 그림과 같이 각 노드의 왼쪽에 있는 빨간색 점을 선으로 쭉 이어보면 전위순회가 완성된다. 중위순회와 후위순회도 마찬가지로 각각 초록색, 파란색 점을 선으로 이어보면 구할 수 있다.  

#include <iostream>
using namespace std;

//전위순회
void pre(int v, int n){
	if(v > n) return;
	else {
		cout << v << " ";
		pre(v*2, n);
		pre(v*2+1, n);
	}
}

//중위순회
void mid(int v, int n){
	if(v > n) return;
	else {
		mid(v*2, n);
		cout << v << " ";
		mid(v*2+1, n);
	}
}

//후위순회
void aft(int v, int n){
	if(v > n) return;
	else {
		aft(v*2, n);
		aft(v*2+1, n);
		cout << v << " ";
	}
}

int main() {
	//freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	
	int n;
	cin >> n;
	
	pre(1, n);
	cout << endl;
	mid(1, n);
	cout << endl;
	aft(1, n);

	return 0;
}

    사이트의 답안   

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;	
void D(int x){
	if(x>7) return;
	else{
		printf("%d ", x);
		D(x*2);
		D(x*2+1);
	}
}	
int main(){
	freopen("input.txt", "rt", stdin);
	D(1);
	return 0;
}

    5번 문제   

    내가 풀이한 답   

 4번 문제와 똑같은 방법으로 풀었고 단순히 인접행렬을 인접리스트 방식으로 바꾸었다. 문제에서 입력 예제를 인접리스트로 나타내면 다음과 같다. 각각의 벡터들이 다른 인덱스값을 가지고 있고 인덱스 하나에 두 개의 값이 들어 있다. 하나는 간선으로 연결될 종점과 나머지 하나는 가중치 값이다. 

//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
using namespace std;

vector<pair<int, int> > map[21];
vector<int> check(21);
int n, minValue = 77777, temp = 0;

int dfs(int v){
	if(v==n) {
		if(minValue > temp) minValue = temp;
	}
	else {
		for(int i=0; i<map[v].size(); i++){
			if(check[map[v][i].first] == 0){
				check[map[v][i].first] = 1;
				temp += map[v][i].second;
				dfs(map[v][i].first);
				check[map[v][i].first] = 0;
				temp -= map[v][i].second;
			}
		}
	}
}

int main() {
	//freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	
	int m, i, a, b, c; 
	cin >> n >> m;
	
	for(i=0; i<m; i++){
		cin >> a >> b >> c;
		map[a].push_back({b, c});
	}
	
	check[1] = 1;
	dfs(1);

	cout << minValue;
	return 0;
}

 결과는 통과하였다.

    사이트의 답안   

#include<stdio.h>
#include<vector>
#include<algorithm>
#define x first
#define y second
using namespace std;	
int ch[30], cnt=0, n, cost=2147000000;
vector<pair<int, int> > map[30];

void DFS(int v, int sum){
	int i;
	if(v==n){
		if(sum<cost) cost=sum;
	}
	else{
		for(i=0; i<map[v].size(); i++){
			if(ch[map[v][i].x]==0){
				ch[map[v][i].x]=1;
				DFS(map[v][i].x, sum+map[v][i].y);
				ch[map[v][i].x]=0;
			}
		}
	}
}
				
int main(){
	freopen("input.txt", "rt", stdin);
	int m, i, a, b, c;
	scanf("%d %d", &n, &m);
	for(i=1; i<=m; i++){
		scanf("%d %d %d", &a, &b, &c);
		map[a].push_back(make_pair(b, c));
	}
	ch[1]=1;
	DFS(1, 0);
	printf("%d\n", cost);
	return 0;
}

    4번 문제   

    내가 풀이한 답   

 앞에서 풀었던 경로 탐색에서 조금 변형된 문제라고 생각했다. 기존에는 간선에 1 값을 넣었는데 1 값 대신에 가중치 값을 넣었고 temp 변수를 하나 선언하고 종점에 도달하기 전까지 더해서 종점에 도착하면 최솟값과 비교하는 것을 생각했다. 주의할 점은 아래 그림에서 두 번째 경로를 찾을 때 2-3, 3-4번으로 가는 가중치 값을 빼주는 것처럼 check값이 0으로 변할 때 temp에 가중치값도 빼줘야 한다. 

//#include <bits/stdc++.h>
#include <iostream>
using namespace std;

int map[21][21], check[21], n, minValue=77777, temp=0;

int dfs(int v){
	if(v==n){
		if(minValue > temp) minValue = temp;
	}
	else {
		for(int i=1; i<=n; i++){
			if(map[v][i]!=0 && check[i] == 0){
				check[i] = 1;
				temp += map[v][i];
				dfs(i);
				check[i] = 0;
				temp -= map[v][i];
			}
		}
	}
}

int main() {
	//freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	
	int m, i, a, b, c;
	cin >> n >> m;
	
	for(i=0; i<m; i++){
		cin >> a >> b >> c;
		map[a][b] = c;
	}

	check[1] = 1;
	dfs(1);

	cout << minValue;
	return 0;
}

 결과는 통과하였다.

    사이트의 답안   

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int map[30][30], ch[30], n, cost=2147000000;	

void DFS(int v, int sum){
	int i;
	if(v==n){
		if(sum<cost) cost=sum;
	}
	else{
		for(i=1; i<=n; i++){
			if(map[v][i]>0 && ch[i]==0){
				ch[i]=1;
				DFS(i, sum+map[v][i]);
				ch[i]=0;
			}
		}
	}
}
int main(){
	freopen("input.txt", "rt", stdin);
	int m, i, a, b, c;
	scanf("%d %d", &n, &m);
	for(i=1; i<=m; i++){
		scanf("%d %d %d", &a, &b, &c);
		map[a][b]=c;
	}
	ch[1]=1;
	DFS(1, 0);
	printf("%d\n", cost);
	
	return 0;
}

 사이트의 답은 sum 값을 dfs 파라미터 인자로 넘겨주고 stack의 특성을 이용해서 sum 값이 stack에 저장되도록 하였다. 

    3번 문제   

    내가 풀이한 답   

 논리적인 흐름은 바뀌지 않고 자료 구조만 바뀌었다. 기존에 이차원 배열이었던 것을 21개의 벡터로 선언하였고 방문 체크를 위한 일차원 배열도 21 크기의 벡터 하나를 선언하였다. 

//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
using namespace std;

vector<int> map[21], check(21);
int n, cnt=0;

void dfs(int v){
	if(v==n) cnt++;
	else {
		for(int i=0; i<map[v].size(); i++){
			if(check[map[v][i]]==0){
				check[map[v][i]] = 1;
				dfs(map[v][i]);
				check[map[v][i]] = 0;
			}
		}
	}
}
 
int main() {
	freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	
	int m, i, a, b;
	cin >> n >> m;
	
	for(i=0; i<m; i++){
		cin >> a >> b;
		map[a].push_back(b);
	}
	
	check[1] = 1;
	dfs(1);
	
	cout << cnt;

	return 0;
}

 결과는 통과하였다.

    사이트의 답안   

#include<stdio.h>
#include<vector>
using namespace std;
int ch[30], cnt=0, n;		
vector<int> map[30];
void DFS(int v){
	int i;
	if(v==n){
		cnt++;
	}
	else{
		for(i=0; i<map[v].size(); i++){
			if(ch[map[v][i]]==0){
				ch[map[v][i]]=1;
				DFS(map[v][i]);
				ch[map[v][i]]=0;
			}
		}
	}
}			
int main(){
	freopen("input.txt", "rt", stdin);
	int m, i, a, b;
	scanf("%d %d", &n, &m);
	for(i=1; i<=m; i++){
		scanf("%d %d", &a, &b);
		map[a].push_back(b);
	}
	ch[1]=1;
	DFS(1);
	printf("%d\n", cnt);
	return 0;
}

    2번 문제   

    내가 풀이한 답   

 문제에서는 7 X 7 형태로 정해져 있었지만 이해를 위해 3 X 3을 기준으로 생각을 해보았다. 한 좌표에서 위, 아래, 오른쪽, 왼쪽을 접근하려면 더 큰 인덱스가 필요했다. 그 결과 (N+2) X (N+2) 형태면 가능하다고 보았다. 아래 그림에서 도착점까지 갈 수 있는 방법은 총 두 가지고 그 중 한 가지의 시퀀스는 다음과 같다. →, ↓, ←, ↑ 순서로 탐색한다고 가정했다.

//#include <bits/stdc++.h>
#include <iostream>
using namespace std;

int map[9][9], check[9][9], cnt = 0;
int x[4] = {1, 0, -1, 0};
int y[4] = {0, 1, 0, -1};

void dfs(int a, int b){
	int xx, yy, i;
	if(a==7 && b==7) cnt++;
	else {
		for(i=0; i<4; i++){
			xx = x[i] + a;
			yy = y[i] + b;
			
			if(xx < 1 || yy < 1 || xx > 7 || yy > 7) continue;
			if(map[xx][yy] == 0 && check[xx][yy] == 0){
				check[xx][yy] = 1;
				dfs(xx, yy);
				check[xx][yy] = 0;
			}
		}
	}
}

int main() {
	//freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	
	int i, j;
	
	for(i=1; i<=7; i++){
		for(j=1; j<=7; j++){
			cin >> map[i][j];		
		}
	}	
	
	check[1][1] = 1;
	dfs(1, 1);
	
	cout << cnt;
	
	return 0;
}

 결과는 통과하였다.

    사이트의 답안   

#include<stdio.h>
int map[10][10], ch[10][10];
int dx[4]={1, 0, -1, 0};
int dy[4]={0, 1, 0, -1};
int cnt=0;

void DFS(int x, int y){	
	int xx, yy, i;
	if(x==7 && y==7){
		cnt++;
	}
	else{
		for(i=0; i<4; i++){
			xx=x+dx[i];
			yy=y+dy[i];
			if(xx<1 || xx>7 || yy<1 || yy>7)
				continue;
			if(map[xx][yy]==0 && ch[xx][yy]==0){
				ch[xx][yy]=1;
				DFS(xx, yy);
				ch[xx][yy]=0;
			}		
		}
	}
}

int main(){
	freopen("input.txt", "r", stdin);
	int i, j;
	for(i=1; i<=7; i++){
		for(j=1; j<=7; j++){
			scanf("%d", &map[i][j]);
		}
	}
	ch[1][1]=1;
	DFS(1, 1);
	printf("%d\n", cnt);
	return 0;
}

    1번 문제   

    내가 풀이한 답   

 문제에 있는 예제는 다음과 같은 과정을 거친다. check 배열을 통해 이미 접근한 노드에 다시 접근하는 것을 방지하고 dfs 재귀 함수를 호출하였다.

//#include <bits/stdc++.h>
#include <iostream>
using namespace std;

int map[21][21], check[21], n, cnt=0;

void dfs(int v){
	if(v==n) cnt++;
	else {
		for(int i=1; i<=n; i++){
			if(map[v][i] == 1 && check[i] == 0){
				check[i] = 1;
				dfs(i);
				check[i] = 0;
			}
		}
	}
}

int main() {
	//freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	
	int m, i, a, b;
	cin >> n >> m;
	
	for(i=0; i<m; i++){
		cin >> a >> b;
		map[a][b] = 1;
	}
	
	check[1] = 1;
	dfs(1);
	
	cout << cnt;
	return 0;
}

 결과는 통과하였다.

    사이트의 답안   

<경로도 함께 출력하는 코드>
#include<stdio.h>	
int map[30][30], ch[30], cnt=0, n, path[30];
void DFS(int v, int L){
	int i, j;
	if(v==n){
		cnt++;
		for(j=0; j<L; j++){
			printf("%d ", path[j]);
		}
		puts("");
	}
	else{
		for(i=1; i<=n; i++){
			if(map[v][i]==1 && ch[i]==0){
				ch[i]=1;
				path[L]=i;
				DFS(i, L+1);
				ch[i]=0;
			}
		}
	}
}
				
int main(){
	freopen("input.txt", "rt", stdin);
	int m, i, j, a, b, c;
	scanf("%d %d", &n, &m);
	for(i=1; i<=m; i++){
		scanf("%d %d", &a, &b);
		map[a][b]=1;
	}
	ch[1]=1;
	path[0]=1;
	DFS(1, 1);
	printf("%d\n", cnt);
	return 0;
}