기록을

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;
}

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

설정은 단순하다. 0이 갈 수 있는 길이고, 1이 벽인데, 벽이 있는 곳을 딱 한 번 부시고 지나갈 수 있다.

이것을 구현하면 되는 것인데

처음에는 단순하게 구조체를 선언해서, 벽을 부실 수 있는 상태인지 관리했다.

즉 한 번 벽을 부수면 앞으로는 벽을 부실 수 없는 것이다.

이것을 구현한 결과는 아래와 같다. 이렇게 구현하지 말라고 보여주는 것이고 잘못된 코드이다

7 4
0000
1110
0000
0111
0000
0011
0010

이것이 반례가 될 수 있다.

#include<iostream>
#include<string>
#include<queue>
using namespace std;
int m[1002][1002], N, M, dis[1002][1002];
struct info {
	int row;
	int col;
	bool brkAbl;
};
queue<info> q;
int dr[4] = { 0,0,1,-1 };
int dc[4] = { -1,1,0,0 };
 void bfs(pair<int, int> start) {
	q.push({start.first, start.second, true});
	dis[start.first][start.second]++;
	while (!q.empty()) {
		info cur = q.front();
		q.pop();
		cout << '\n'; cout << '\n';
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				cout << dis[i][j] << ' ';
			}
			cout << '\n';
		}
		for (int i = 0; i < 4; i++) {
			
			int nr = cur.row + dr[i];
			int nc = cur.col + dc[i];

			if (nr < 1 || nc < 1 || nr > N || nc > M || dis[nr][nc] > 0) continue;
			
			//벽만났는데, 벽을 부실 수 있는 경우
			if (m[nr][nc] == 1 && cur.brkAbl) {
				//cur.brkAbl = false;
				q.push({ nr, nc, false });
				dis[nr][nc] = dis[cur.row][cur.col] + 1;
			}
			//벽이 아닌 경우 -> 현재 상태의 벽부시기 가능 여부를 같이 넘겨줌
			else if (m[nr][nc] == 0) {
				q.push({ nr, nc, cur.brkAbl });
				dis[nr][nc] = dis[cur.row][cur.col] + 1;
			}
		}
	}
}
int main(void) {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		string temp;
		cin >> temp;
		for (int j = 1; j <= M; j++) {
			m[i][j] = temp[j - 1] - '0';
		}
	}
	bfs({ 1, 1 });
	if (dis[N][M] != 0)
		cout << dis[N][M] << '\n';
	else
		cout << -1 << '\n';
	return 0;
}

그런데 문제가 있다. 상황이 단순하지 않은 것이, 특정 지점까지 갈 때, 벽을 부시는 것이 최단 경로가 될 수 있다.

이때, 특정 지점까지 벽을 부수고 최단으로 갔는데, 정작 끝까지 도달하려면 벽을 반드시 부숴야 하는 경우가 있다.

즉 조금 더 길게 가더라도, 마지막에 도착지까지 가려면 벽을 부수지 않아야 한다는 것이다.

따라서 단순히 벽을 부실 수 있는지 아닌지 여부만 관리할 게 아니라, 벽을 부수었다는 것과 방문처리(거리) 관리를 동시에 해주어야 한다는 것이다.

#include<iostream>
#include<string>
#include<queue>
using namespace std;
int m[1002][1002], N, M, dis[1002][1002][2];
struct info {
	int row;
	int col;
	int blk; //1이면 부시기 가능
};
queue<info> q;
int dr[4] = { 0,0,1,-1 };
int dc[4] = { -1,1,0,0 };
 void bfs() {
	q.push({ 1,1,1 });
	dis[1][1][1] = 1; //벽부시기 가능이니까 [1]에 넣음


	while (!q.empty()) {
		info cur = q.front();
		q.pop();
		
		if (cur.row == N && cur.col == M) {
			cout << dis[cur.row][cur.col][cur.blk] << '\n';
			return;
		}

		for (int i = 0; i < 4; i++) {
			
			int nr = cur.row + dr[i];
			int nc = cur.col + dc[i];

			if (nr < 1 || nc < 1 || nr > N || nc > M) continue;
			
			//벽 만났는데 부실 수 있는 경우
			if (m[nr][nc] == 1 && cur.blk == 1) {
				q.push({ nr, nc, 0 }); //이후로는 부실수 없음
				dis[nr][nc][0] = dis[cur.row][cur.col][1] + 1;
			}
			//벽 아닌 경우
			else if (m[nr][nc] == 0 && dis[nr][nc][cur.blk] == 0) {
				q.push({ nr, nc, cur.blk });
				dis[nr][nc][cur.blk] = dis[cur.row][cur.col][cur.blk] + 1;
			}
		}
	}
	cout << -1 << '\n';
	return;
}
int main(void) {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		string temp;
		cin >> temp;
		for (int j = 1; j <= M; j++) {
			m[i][j] = temp[j - 1] - '0';
		}
	}
	
	bfs();

	//for (int i = 0; i < 2; i++) {
	//	for (int j = 1; j <= N; j++) {
	//		for (int k = 1; k <= M; k++) {
	//			cout << dis[j][k][i] << ' ';
	//		}
	//		cout << '\n';
	//	}
	//	cout << '\n'; cout << '\n';
	//}
	//
	return 0;
}

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

쉽게 풀려면 쉽게 풀 수 있는 문제이다.

문제를 살펴보자. 먼저 같은 숫자가 여러 번 등장할 수 있다는 조건이 있다.

즉 1 9 9 이런식으로 숫자의 목록이 있다면, 길이 2의 수열이 19 19 91 99 91 99 이렇게 3p2개 나올 수 있다는 것이다.

이제 중복을 제거해줘야 하고, 오름차순으로 정렬을 해줘야 한다.

정렬 방법은, 지금까지 그래 왔던 것처럼 미리 사용 가능 숫자들을 정렬해주면 된다.

또한 중복을 제거할 때는, 여러가지 방법이 물론 있겠지만, 간단하게 중복을 허용하지 않는 set을 사용했다.

set에 어떤 data를 삽입할 때, 이미 같은 데이터가 set 내부에 존재하면, 삽입 시도는 무시된다.

그런데 이번 문제를 풀던 도중 새로운 사실을 알았다.

처음에는 string type으로 공백과 함께 set에 담아서 출력을 하려고 했다.

따라서 set<string> 이렇게 타입을 잡았는데, set 안에 들어가게 되면 string을 나중에 꺼내서 사용할 때 string의 길이가 1이 된다는 것이다. 즉 string이 내가 평소에 아는 string이 아니게 된다.

이 문제를 해결하기 위해 set안에 vector을 넣기로 하고 문제를 해결했다. vector는 이상 없이 작동했다.

#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
int n, m, arr[11], num[11];
bool isused[11];
set<vector<int> > ctnr;
void func(int k) {
	if (k == m + 1) {
		vector<int> v;
		for (int i = 1; i <= m; i++) {
			v.push_back(arr[i]);
		}
		ctnr.insert(v);
		v.clear();
		return;
	}
	
	for (int i = 1; i <= n; i++) {
		if (!isused[i]) {
			arr[k] = num[i];
			isused[i] = true;
			func(k + 1);
			isused[i] = false;
		}
	}
}
int main(void) {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> num[i];
	sort(num + 1, num + 1 + n);

	func(1);

	/*for (set<string>::iterator i = ctnr.begin(); i != ctnr.end(); i++) {
		for (int j = 0; j < (*i).length(); j++) {
			if (j % 2 == 0) cout << stoi((*i).substr(j, 1));
			else cout << ' ';
		}
		cout << '\n';
	}*/
	for (auto e : ctnr) {
		for (int i = 0; i < e.size(); i++) {
			cout << e[i] << ' ';
		}
		cout << '\n';
	}
	return 0;
}

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

사용할 수 있는 수들을 오름차순 정렬한다.

이전 자리에서 사용한 숫자보다 다음에 사용할 자리의 숫자가 크거나 같으면 된다.

숫자를 중복해서 사용할 수 있으니, 숫자의 사용 여부를 관리하는 배열도 필요하지 않다.

#include<iostream>
#include<algorithm>
using namespace std;
int num[9], arr[9];
int n, m;
void func(int k) {
	if (k == m + 1) {
		for (int i = 1; i <= m; i++)
			cout << arr[i] << ' ';
		cout << '\n';
		return;
	}
	
	for (int i = 1; i <= n; i++) {
		if (arr[k - 1] > num[i]) continue; //k가 1이면 arr[] = 0 이라서 상관X
		else {
			arr[k] = num[i];
			func(k + 1);
		}
	}
}
int main(void) {
	
	cin >> n >> m;
	//n개 가지고 길이 m
	for (int i = 1; i <= n; i++)
		cin >> num[i];
	sort(num + 1, num + 1 + n);
	func(1);
	return 0;
}

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

R G B 각각으로 이루어진 영역의 개수를 찾으면 되는 문제였다.

추가적인 경우는 R과 G를 같게 보고 위의 작업을 반복해주면 된다.

첫 번째 경우를 처리한 이후에 R성분을 G로 바꿔서 같은 작업을 반복했다.

주의할 사항은 입력을 받는 것이다. m을 이차원 char 배열로 잡아두고, string으로 한 줄씩 입력을 받았다.

#pragma warning(disable:4996)
#include<iostream>
using namespace std;
char m[101][101];
bool vis[101][101];
int N;
int dr[4] = { 0,0,1, -1 };
int dc[4] = { 1,-1,0,0 };
int cnt1 = 0, cnt2 = 0;
bool norCheck(int nr, int nc, char c) {
	if (nr < 0 || nc < 0 || nr >= N || nc >= N || vis[nr][nc] || m[nr][nc] != c)
		return true;
	else
		return false;
}

void dfs(int row, int col, char c) {
	vis[row][col] = true;
	
	for (int i = 0; i < 4; i++) {
		int nr = row + dr[i];
		int nc = col + dc[i];

		if (norCheck(nr, nc, c)) continue;
		dfs(nr, nc, c);
	}
}
int main(void) {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> m[i];
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (!vis[i][j]) {
				dfs(i, j, m[i][j]);
				cnt1++;
			}
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (m[i][j] == 'R') m[i][j] = 'G';
			vis[i][j] = false;
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (!vis[i][j]) {
				dfs(i, j, m[i][j]);
				cnt2++;
			}
		}
	}
	cout << cnt1 << ' ' << cnt2 << '\n';

	return 0;
}

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

나이트가 현재 위치에서 특정 위치로 이동할 때, 이동 횟수를 구하는 것이다.

나이트가 한번 움직일 때 이동 거리가 1이라고 생각한다면, 최단거리를 구하는 문제로 이해할 수 있다

따라서 bfs로 접근하되, 나이트의 움직임을 표현해주면 되겠다.

새로운 위치가 큐에 삽입될 때, 추가되는 위치가 목적지인지 비교하고, 만약 목적지라면 bfs를 끝낸다.

보통의 bfs는 큐가 빌 때 종료되는데, 이번 문제는 그렇지 않다.

따라서 여러 개의 테스트 케이스를 처리할 때 다른 변수들과 마찬가지로 큐 또한 비워주는 것이 중요하다.

#include<iostream>
#include<queue>
using namespace std;
int n, dist[301][301];
queue<pair<int, int> >q;
int dr[8] = { -1, -2, -2, -1, 1, 2, 2, 1 };
int dc[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
void bfs(pair<int, int> Src, pair<int, int> Dst) {
	q.push(Src);
	dist[Src.first][Src.second]++;
	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();
		for (int i = 0; i < 8; i++) {
			int nr = cur.first + dr[i];
			int nc = cur.second + dc[i];
			
			if (nr < 0 || nc < 0 || nr >= n || nc >= n || dist[nr][nc] >= 0) continue;
			
			q.push({ nr, nc });
			dist[nr][nc] = dist[cur.first][cur.second] + 1;
			if (nr == Dst.first && nc == Dst.second) return; //이후에 큐 비우기
		}
	}
}
int main(void) {
	int tc;
	cin >> tc;
	while (tc--) {
		cin >> n;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				dist[i][j] = -1;
			}
		}
		pair<int, int> src, dst;
		cin >> src.first >> src.second >> dst.first >> dst.second;
		bfs(src, dst);

		cout << dist[dst.first][dst.second] << '\n';
		
		//초기화
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				dist[i][j] = -1;
			}
		}
		while (!q.empty()) q.pop(); //queue가 비워지지 않은 상태로 bfs가 끝난다
	}
	return 0;
}

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

숫자를 중복해서 뽑을 수 있기 때문에 숫자의 사용 여부를 관리하는 배열이 필요가 없다.

num배열에 사용할 수 있는 수들을 입력받고 정렬해준다.

#include<iostream>
#include<algorithm>
using namespace std;
int N, M, num[8], arr[8];

void func(int k) {
	if (k == M + 1) {
		for (int i = 1; i <= M; i++) {
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}
	
	for (int i = 1; i <= N; i++) {
		arr[k] = num[i]; //k번째 자리로 i번째 숫자 선택
		func(k + 1); //k+1번째 자리 정하기
	}
}
int main(void) {
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
		cin >> num[i];
	sort(num + 1, num + N + 1); //수열이 오름차순으로 나오게 하기 위해 오름차순 정렬
	func(1); //1번째 자리를 선택할 차례

	return 0;
}

큐를 활용한 BFS 풀이가 궁금하다면 아래 글을 참고하기 바란다.

 https://hugssy.tistory.com/56?category=843457

평소 무의식적으로 bfs로만 풀이를 진행한 것 같아서, 이렇게 가끔 bfs로 풀이했던 문제들을 DFS로 풀이해보려고 한다.

확실히 코드가 간결해지긴 하는 것 같다. 무리 없이 재귀를 따라갈 수 있다면 쉽게 사용할 수 있을 것 같다.

일단 큐 따위를 사용하지 않기 때문에 pair 자료구조도 사용할 필요 없이 그냥 dfs 함수의 인자로는 row 값과 col 값을 담으면 되겠다.

방문한 적 없는 지점이면서 집이 있는 지점에서 최초로 dfs를 시작한다. 즉 main 함수에서 dfs를 실행시키는 것이, 새로운 단지를 찾았다는 것이 되겠다. 따라서 main 함수에서 dfs를 몇 번 수행하는지를 계산하면 단지의 전체 수를 찾을 수 있겠다.

필자는 이것을 벡터로 처리했다. 벡터를 사용하면 단지의 개수가 총 몇 개 나올 것인지 생각할 필요가 없기 때문에 좀 더 편하고 빠르게 문제를 풀 수 있다.

dfs 함수 내에서는, 범위 조건을 만족하고, 방문할 가치가 있는 곳이라면 이어서 dfs를 수행한다.

이어서 dfs를 실행할 상황이 온다는 것은, 곧 집을 하나 더 찾았다는 것을 의미한다.

이때 처음 dfs를 수행하기 시작한 곳도 집이라는 것을 생각해서 homeCnt를 1로 초기화해줘야 한다.

main 함수에서 한 번의 dfs가 모두 끝났다는 것은 단지 하나를 전부 돌았다는 것이다.

따라서 이 타이밍에 집의 개수를 추가해주고 다시 집의 개수를 초기화해주면 되겠다.

#pragma warning(disable :4996)
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n, m[26][26];
bool vis[26][26];
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
int homeCnt = 1;
vector<int> v;
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 >= n || nc >= n) continue;
		if (vis[nr][nc] || m[nr][nc] == 0) continue;
		
		homeCnt++;
		dfs(nr, nc);
	}
}

int main(void) {
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			scanf("%1d", &m[i][j]);
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!vis[i][j] && m[i][j] == 1) {
				dfs(i, j);
				v.push_back(homeCnt);
				homeCnt = 1;
			}
		}
	}
	sort(v.begin(), v.end());

	cout << v.size() << '\n';
	for (int i = 0; i < v.size(); i++)
		cout << v[i] << '\n';
	return 0;
}

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

문제 설명

방문 처리가 되지 않은 지점이면서 집인 경우에 bfs를 수행해준다.

한 번 수행할 때마다 단지를 하나씩 찾게 되므로, bfs 함수가 실행될 때 단지의 수를 증가시킨다.

이어서 각 단지마다 집의 개수를 파악해야 한다.

이는 bfs를 수행하면서 큐에 push 되는 횟수를 저장해주면 된다. 당연하게도 집인 경우에만 다음에 이어서 탐색을 하도록 구현했으니까.

주의할 것은, 시작지점 즉 bfs를 시작하는 지점도 집이라는 사실이다. 따라서 단지 내 집의 개수를 저장하는 변수인 homeCnt를 1로 초기화했다.

그리고 초기에는 단지 전체의 수를 저장할 변수도 있었는데, 벡터를 사용하게 되면 벡터의 크기가 곧 단지의 개수가 될 것이기 때문에 이것으로 대신했다.