기록을

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

숫자의 입력이 중복되어서 들어올 수 있다.

결과로 나오는 수열은 오름차순으로 정렬되는 상태여야 한다. 하지만 입력은 정렬되어서 들어오는 것이 아니기 때문에 입력을 모두 받은 이후에 오름차순 정렬을 해줘야 한다.

또한, 사용했던 숫자를 재사용할 수 있기 때문에 숫자의 사용 중 여부를 판단하는 배열 또한 필요하지 않다.

그리고 수열이 중복되어서 생성될 수 있는데, 이는 중복을 허용하지 않는 set을 활용해서 처리했다.

#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
int m, n, arr[7], num[7];
set<vector<int > > st;
vector<int> v;
void func(int k) {
	if (k == m) {
		for (int i = 0; i < m; i++) {
			v.push_back(arr[i]);
		}
		st.insert(v);
		v.clear();
		return;
	}
	for (int i = 0; i < n; i++) {
		arr[k] = num[i];
		func(k + 1);
	}
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> num[i];
	sort(num, num + 1);
	func(0); //0번까지 채워져있다
	set<vector<int> >::iterator itr;
	for (itr = st.begin(); itr != st.end(); itr++) {
		vector<int> tmp = *itr;
		for (int i = 0; i < tmp.size(); i++)
			cout << tmp[i] << ' ';
		cout << '\n';
	}
	return 0;
}

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

n개의 숫자중에 6개를 뽑아서 수열을 만들고, 오름차순 정렬하여 출력해주면 된다.

입력으로 들어오는 숫자는 정렬된다는 조건이 없다는 것을 주의해야 한다.

1. next_permutation 활용 구현

#include<iostream>
#include<algorithm>
using namespace std;
int n, a[50], Sel[50];
int main(void) {
	while (1) {
		cin >> n;
		if (n == 0) return 0;
		
		for (int i = 0; i < n; i++)
			cin >> a[i];
		sort(a, a + n);
		for (int i = 0; i < n; i++) {
			if (i < 6) Sel[i] = 0;
			else Sel[i] = 1;
		}
		
		do {
			for (int j = 0; j < n; j++) {
				if (!Sel[j]) cout << a[j] << ' ';
			}
			cout << '\n';
		} while (next_permutation(Sel, Sel + n));
		cout << '\n';
	}
	return 0;
}

2. 백트래킹 활용 구현

마찬가지로 사용할 수 있는 수들을 입력 받은 이후에, 수열을 오름차순으로 만들어내기 위해서 정렬을 수행한다.

조합이기 때문에 매 재귀마다 0부터 확인하는 것이 아니라 이전 재귀에서 사용했던 숫자의 위치를 파악해서 그 숫자 이후로 사용할 수 있는 숫자를 찾는다.

#include<iostream>
#include<algorithm>
using namespace std;
int n, num[50], arr[7];
bool isused[50];
int st;
void func(int k) {
	//여기서 수열의 길이 k
	if (k == 6) {
		for (int i = 0; i < k; i++) {
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}
	
	if (k == 0) st = 0; //0일때 초기화
	for (int i = st; i < n; i++) { //조합으로 만들기 위해 st부터. 0부터 뽑으면 순열(순서가 다르면 다른 수열)
		if (!isused[i]) {
			isused[i] = true;
			arr[k] = num[i];
			st = i;
			func(k + 1);
			isused[i] = false;
		}
	}
}
int main(void) {
	while (1) {
		cin >> n;
		if (n == 0) break;
		for (int i = 0; i < n; i++) {
			cin >> num[i];
		}
		sort(num, num + n);
		func(0);
		cout << '\n';
	}
}

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

두 가지를 동시에 신경써야 했다. 불의 확산과 사람의 이동.

특히 신경써야 할 부분은

1. 이제 불이 붙으려는 칸으로 이동할 수 없다

2. 현재 위치로 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

이 두가지이다.

기본적인 접근은 불을 먼저 확산시킬 것인가, 사람을 먼저 움직일 것인가를 결정하는 것이다.

1. 불의 확산 이후 사람의 이동

불을 먼저 확산시키면 사람의 위치가 지워질 가능성이 높다. 따라서 사람의 시작 위치를 미리 관리해주어야 한다.

이후에는 사람의 이동거리(매 초 사람의 위치)를 따로 둘 것이기 때문에 초반에 불의 이동에 의해서 @의 위치가 손실되는 것만 신경써주면 이후로는 신경쓸 부분이 없다. 즉 위에서 신경써야 할 부분이라고 언급한 2번 조건이 상관 없어지는 것이다.

당연하게도 불을 먼저 확산시켰으므로 불이 붙으려는 칸으로는 당연하게 이동할 수 없다. 구현을 그렇게 했으니까.

2. 사람의 이동 이후 불의 확산

이 방식은 먼저 사람의 이동을 고려한다. 당연하게도 이동하려는 곳은 비어있는(불도 벽도 아닌) 곳이어야 한다.

그리고 그 이동하려는 곳의 4방향을 미리 탐색해서 불이 있는지 없는지를 확인해야 한다. 이것으로 신경써야 할 부분 1을 피할 수 있다.

즉 사람의 이동을 구현하는 데에 두 단계가 필요하다는 것이다.

또한 사람의 이동을 먼저 구현했기 때문에, 이미 이동한 뒤에 불이 확산하는 것이므로 원래 사람이 있던 자리에 불이 번지는 것은 이제 상관이 없어진다. 이렇게 신경써야 할 부분 2를 해결할 수 있다.

두 가지 모두 생각해 본 결과, 1의 구현이 더 간단한 것 같았으므로 1번으로 구현 방향을 잡았다.

#include<iostream>
#include<queue>
using namespace std;
int Col, Row, dis[1001][1001]; //dis로 사람의 매초 위치(그 지점까지 최단거리)를 관리
char m[1001][1001]; //빌딩 상태
bool Fire[1001][1001]; //불의 존재 여부 관리
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
queue<pair<int, int> > fireQ; //불의 번짐을 관리할 큐
queue < pair<int, int> > q; //사람의 이동을 관리할 큐
void Fbfs() {
	while (!q.empty()) { //사람이 움직일 위치가 없으면 더 이상의 진행이 무의미

		int num = fireQ.size(); //매 초 있던 불꽃으로만 확산 진행
		while (num--) { 
			pair<int, int> cur = fireQ.front();
			fireQ.pop();
			for (int i = 0; i < 4; i++) {
				int nr = cur.first + dr[i];
				int nc = cur.second + dc[i];
				if (nr < 0 || nc < 0 || nr >= Row || nc >= Col) continue;
				if (m[nr][nc] == '#' || Fire[nr][nc]) continue; //벽 or 이미 불이 존재하는 곳이면 continue
				//printf("\n%d %d 추가\n", nr, nc);
				fireQ.push({ nr, nc });
				Fire[nr][nc] = true;
				m[nr][nc] = '*';
			}
		}

		int Run = q.size(); //불과 마찬가지로 매초 한칸씩 움직이게 통제
		while (Run--) {
			pair<int, int> cur = q.front();
			q.pop();
			for (int i = 0; i < 4; i++) {
				int nr = cur.first + dr[i];
				int nc = cur.second + dc[i];
				if (nr < 0 || nc < 0 || nr >= Row || nc >= Col) {
					//탈출처리 -> 건물 끝까지 가는데 n초 걸렸고, 이제 넘어가니까 +1
					cout << dis[cur.first][cur.second] + 1 << '\n';
					return;
				}
				if (dis[nr][nc] >= 0 || m[nr][nc] != '.')continue; //이미 지나온 길이거나 이동할 수 있는 길이 아니면 continue
				q.push({ nr, nc });
				dis[nr][nc] = dis[cur.first][cur.second] + 1;
			}
		}
	}
	cout << "IMPOSSIBLE" << '\n';
}
void init() {
	for (int i = 0; i < Row; i++) {
		for (int j = 0; j < Col; j++) {
			dis[i][j] = -1; // 0이상이면 사람이 거쳐간 상태(방문 완료)
			Fire[i][j] = false;
 		}
	}
	while (!q.empty()) q.pop(); //탈출 조건에서 큐가 비지 않았는데 함수가 종료됨
	while (!fireQ.empty()) fireQ.pop();
}
int main() {
	int T;
	cin >> T;
	while (T--) {
		cin >> Col >> Row;
		
		init(); //TC가 여러개, 큐를 완전히 비우지 않고 끝내는 경우도 있으므로 큐도 초기화
		for (int i = 0; i < Row; i++) {
			for (int j = 0; j < Col; j++) {
				cin >> m[i][j];
				if (m[i][j] == '@') { //사람의 시작 위치를 담아둬야함. 불이 덮어 쓰기 때문에
					q.push({ i, j }); 
					dis[i][j]++;
				}
			}
		}
		

		for (int i = 0; i < Row; i++) {
			for (int j = 0; j < Col; j++) {
				if (m[i][j] == '*' && !Fire[i][j]) {
					fireQ.push({ i, j });
					Fire[i][j] = true;
				}
			}
		}
		Fbfs();
	}
	return 0;
}

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

floodfill을 통해서 빙산이 두 개가 될 때까지 빙산이 녹는 과정을 구현하면 된다. 

빙산이 녹는 것을 구현할 때 주의할 사항은, 녹아서 0이 된 빙산을 같은 해야 원래 녹아있던 것으로 보지 않는 것이다.

이는 방문 처리 배열을 통해서 처리해주면 된다. 녹아서 바다가 되버린 빙산이라도, 방문처리가 되어있기 때문에, 방문 처리가 되지 않은 바다만 빙산을 녹이는 데에 영향을 끼칠 수 있게 구현을 하면 된다.

또 유의할 것은 방문처리 배열의 초기화이다. 빙산을 녹이는 과정과, 빙산의 개수를 파악하기 위해서 floodfill을 하는 과정은 모두 방문처리 배열을 이용한다. 이때 한 번 방문처리 배열을 사용했으면, 바로 초기화를 해줘야 한다.

#include<iostream>
using namespace std;
int R, C, m[300][300];
bool vis[300][300];
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
void dfs(int row, int col) {
	vis[row][col] = true;
	
	for (int i = 0; i < 4; i++) {
		int nr = row + dr[i];
		int nc = col + dc[i];
		
		if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
		if (vis[nr][nc] || m[nr][nc] == 0) continue;
		dfs(nr, nc);
	}
}
int Flood() {
	int res = 0;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (m[i][j] != 0 && !vis[i][j]) {
				res++;
				if (res > 1) break;
				dfs(i, j);
			}
		}
	}
	return res;
}
void init() {
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			vis[i][j] = false;
		}
	}
}
void Melt(int row, int col) {
	vis[row][col] = true;
	int cnt = 0;
	for (int i = 0; i < 4; i++) {
		int nr = row + dr[i];
		int nc = col + dc[i];

		if (nr < 0 || nc < 0 || nr >= R || nc >= C || vis[nr][nc]) continue;
		if (m[nr][nc] == 0) cnt++;
		else if (m[nr][nc] == 1) Melt(nr, nc);
	}
	if (m[row][col] - cnt <= 0) m[row][col] = 0;
	else
		m[row][col] = m[row][col] - cnt;
}

int main() {
	cin >> R >> C;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> m[i][j];
		}
	}

	int year = 0;
	while (1) {
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (m[i][j] != 0 && !vis[i][j]) {
					Melt(i, j);
				}
			}
		}
		year++;
		init();
		if (Flood() > 1) {
			cout << year << '\n';
			break;
		}
		init();
		if (Flood() == 0) {
			cout << 0 << '\n';
			break;
		}
		init();
	}
	return 0;
}

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

정수들의 개수와 목표로 하는 합을 입력받는다.

정수들로 만들 수 있는 길이가 1 이상인 부분 수열들을 구한다. 그리고 그 부분수열들의 합이 처음에 입력받은 S와 같은 부분수열의 개수를 구하면 되는 문제이다.

우선 N개의 숫자를 입력받았다고 가정하면, 1개, 2개, 3개 ... N개로 만들 수 있는 부분수열을 모두 구해야 한다.

그리고 매 부분수열마다 합을 계산해서 그 합이 s인지 아닌지 판단해주면 되는 문제이다.

즉 조합으로 바꿔서 생각할 수 있고, n이 20 이하로 작으니 백트래킹을 해도 무방하다.

직접 재귀로 구현할 수도 있지만 next_permutation을 이용해서 구현했다.

Sel 배열을 우선 만들어 둔다. 가령 6개 중에 4개를 조합으로 뽑는다면,

Sel 배열은 0, 0, 0, 0, 1 1 이렇게 두고 if(!Sel[i]) 일 때 수열이 만들어지게 된다.

이를 이용해서 1개부터 n개까지 부분수열을 구해주면 되겠다.

#include<iostream>
#include<algorithm>
using namespace std;
int n, s, a[20], Sum = 0, Sel[20], cnt = 0;
int main(void) {
	cin >> n >> s;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < 20; i++)
		Sel[i] = 1;
	for (int i = 0; i < n; i++) {
		Sel[i] = 0; //하나씩 0으로 바꿈
		do {
			Sum = 0;
			for (int j = 0; j < n; j++) {
				if (!Sel[j]) Sum += a[j];
				//if (!Sel[j]) cout << a[j] << ' ';
			}
			if (Sum == s) cnt++;
		} while (next_permutation(Sel, Sel + n));
	}
	cout << cnt << '\n';
	return 0;
}

next permutation 기본형은 아래와 같다. 배열(벡터)의 다음 사전순 순서를 반환해준다.

1, 2, 3 ,4를 이용해서 만들 수 있는 모든 길이 4짜리 수열을 만드는 코드는 아래와 같다. (순서가 다르면 다른 수열)

#include<iostream>
#include<algorithm>
using namespace std;
int main(void) {
	int a[4] = { 1,2,3,4 };
	do {
		for (int i = 0; i < 4; i++)
			cout << a[i] << ' ';
		cout << '\n';
	} while (next_permutation(a, a + 4));
	return 0;
}

실행 결과는 위와 같다.

다음으로 6개의 숫자 중에서 2개의 숫자를 조합으로 뽑는 경우는 다음과 같다.

#include<iostream>
#include<algorithm>

using namespace std;
int main(void) {
	int a[6] = { 1,5,3,6,2,7 };
	//sort(a, a + 6);
	int Select[6] = { 0,0,1,1,1,1 }; //이러면 조합
	int cnt = 0;
	do {
		cnt++;
		for (int i = 0; i < 6; i++) 
			if (!Select[i]) cout << a[i] << ' ';
		cout << '\n';
	} while (next_permutation(Select, Select + 6));
	//cout << cnt;
	return 0;
}

Select 배열을 가지고 next_permutation을 돌려준다. 뽑고 싶은 숫자의 개수를 0의 개수로 하고 앞에서부터 0을 써주면 된다. 위의 예시는 정렬을 하지 않았는데, 사용할 수 있는 숫자를 그대로 두고 실행했을 때 어떤 결과가 나오는지 보기 위함이다.

sorting하는 부분의 주석을 풀면, 사전순으로 수열이 정렬되서 나올 것이다.

이제 순열을 구현해보면 다음과 같다. 먼저 배열이 하나 더 필요하다. Select의 값이 0보다 클 때 if문에 진입하게 되고,

Select 값으로 index를 맞춰야 하는데 1부터 시작하므로 1씩 빼서 seq에 담아준 것이다. 

#include<iostream>
#include<algorithm>

using namespace std;
int main(void) {
	int a[6] = { 1,5,3,6,2,7 };
	//sort(a, a + 6);
	int Select[6] = { 0,0,0,0,1,2 }; 
	int cnt = 0;
	do {
		//cnt++;
		int seq[2] = {};
		for (int i = 0; i < 6; i++)
			if (Select[i]) seq[Select[i] - 1] = a[i];
		for (int i = 0; i < 2; i++) cout << seq[i] << ' ';
		cout << '\n';
	} while (next_permutation(Select, Select + 6));
	//cout << cnt;
	return 0;
}

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

퀸은 놓여있는 위치의 행과 열 그리고 대각선 두 방향을 공격할 수 있다.

N이 15 정도밖에 되지 않기 때문에 백트래킹을 해도 충분하다.

먼저 행당 1개의 퀸이 있는 것은 당연하다.

따라서 우리는 특정 열에 퀸을 놓을 수 있는가, 특정 대각선에 퀸을 놓을 수 있는가를 관리해주면 된다.

#include<iostream>
using namespace std;
int n;
bool isused[3][40];
int cnt = 0;
void func(int k) {
	//k-1개 까지 다 놓은 상태
	if (k == n + 1) {
		cnt++;
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (isused[0][i] || isused[1][k + i] || isused[2][k - i + n - 1])
			continue;
		isused[0][i] = true;
		isused[1][k + i] = true;
		isused[2][k - i + n - 1] = true;
		func(k + 1);
		isused[0][i] = false;
		isused[1][k + i] = false;
		isused[2][k - i + n - 1] = false;
	}
}
int main(void) {
	cin >> n;
	func(1);
	cout << cnt;
	return 0;
}

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

퀸이 올라올 수 없는 곳의 위치를 체스판 한 칸 한 칸으로 관리하려고 했다.

그래서 2차원 배열을 활용했는데

초반의 생각은 이러했다.

가령 1,0에 퀸을 놓으면 1,0이 포함된 행과 열 그리고 두 개의 대각선에 퀸을 놀 수 없다.

이때 1,2는 둘 수 없는 위치이다. 그런데 2, 2는 둘 수 있는 위치이고, 2,2에 퀸을 두고 또 2,2를 둠으로써 둘 수 없는 위치를 잡고 나서 재귀를 빠져나올 때, 2,2의 행과 열 그리고 두 대각선의 bool 값을 모두 변경해버리면 1,1가 막고 있었던 것이 풀리게 되어서 제대로 된 연산이 되지 않는다.

따라서 좌표 하나하나를 관리할 게 아니라, 열과 행 그리고 대각선들로 사용중 여부를 관리하는 배열을 잡아야 한다.

#include<iostream>
using namespace std;
int N, m[15][15];
bool isused[15][15];
int cnt = 0;
void usage(int i, int j, bool ctr) {
	isused[i][j] = ctr;
	if (ctr) {
		printf("퀸위치: %d %d'\n", i, j);
	}
	for (int k = 0; k < N; k++) {
		isused[i][k] = ctr;
		isused[k][j] = ctr;
	}
	for (int l = 0; l < N; l++) {
		for (int m = 0; m < N; m++) {
			if (l + m == i + j) isused[l][m] = ctr;
			if (l - m == i - j) isused[l][m] = ctr;
		}
	}
}
void func(int k) {
	if (k == N+1 ) {
		cnt++;
		
		return;
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (!isused[i][j]) {
				usage(i, j, true);
				printf("%d %d에 퀸추가\n", i, j);
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						cout << isused[i][j] << ' '; 
					}cout << '\n';
				}
				cout << '\n'<<'\n';
				func(k + 1);

				//isused[i][j] = false;
				usage(i, j, false);
				printf("%d %d에 퀸제거\n", i, j);
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						cout << isused[i][j] << ' ';
					}cout << '\n';
				}
				cout << '\n' << '\n';
			}
		}
	}
}
int main(void) {
	cin >> N;
	func(1);
	cout << cnt << '\n';
	return 0;
}

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

사용할 수 있는 숫자들 중에 중복되는 숫자가 있을 수 있다.

숫자는 중복해서 사용하면 안 되고 입력받은 개수만큼만 사용해야 하며

만들어낸 수열은 비내림차순이어야 한다.

#include<iostream>
#include<vector>
#include<unordered_set>
#include<set>
using namespace std;
int N, M, arr[9], n[9];
bool isused[9];
set<vector<int> > st;
vector<int> v;
void func(int k) {
	
	if (k == M + 1) {
		for (int i = 1; i <= M; i++) {
			v.push_back(arr[i]);
		}
		st.insert(v);
		v.clear();
		return;
	}

	for (int i = 1; i <= N; i++) {
		if (!isused[i] && arr[k - 1] <= n[i]) {
			isused[i] = true;
			arr[k] = n[i];
			func(k + 1);
			isused[i] = false;
		}
	}
}
int main() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> n[i];
	}
	func(1);
	for (set<vector<int> >::iterator it = st.begin(); it != st.end(); it++) {
		for (int i = 0; i < (*it).size(); i++) {
			cout << (*it)[i] << ' ';
		}
		cout << '\n';
	}
	return 0;
}

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

입력을 받으면서, 입력받는 높이의 최소와 최대를 구해둔다.

1부터 100까지 다 해볼 필요 없이 필요한 것만 해보는 것이다. 문제에서 아무 곳도 잠기지 않는 경우도 있다고 명시했기 때문에 높이 제한의 최소-1부터 최대까지를 물의 높이 변화로 정해주면 된다.

#include<iostream>
using namespace std;
int N, m[102][102];
bool vis[102][102];
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
void dfs(int row, int col, int H) {
	vis[row][col] = true;
	for (int i = 0; i < 4; i++) {
		int nr = row + dr[i];
		int nc = col + dc[i];
		if (nr < 0 || nc < 0 || nr >= N || nc >= N) continue;
		if (vis[nr][nc] || m[nr][nc] <= H) continue;
		dfs(nr, nc, H);
	}
}
void init() {
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			vis[i][j] = false;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	int hMin = 110, hMax = -1;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> m[i][j];
			if (m[i][j] > hMax) hMax = m[i][j];
			if (m[i][j] < hMin) hMin = m[i][j];
		}
	}
	
	int cntMax = 0;
	for (int h = hMin - 1; h <= hMax ; h++) {
		int cntH = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (m[i][j] > h && !vis[i][j]) {
					dfs(i, j, h);
					cntH++;
				}
			}
		}
	
		if (cntH > cntMax) cntMax = cntH;
		init();
	}
	cout << cntMax << '\n';
	return 0;
}