기록을

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로 초기화했다.

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

문제 링크이다.

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

사이클을 탐색할 수 있으면 해결할 수 있는 문제이다.

팀이 결정되는 조건이 결국 사이클을 이루는 조건이기 때문이다.

사이클을 검사할 때 템플릿처럼 활용할 수 있을 것 같다.

먼저 방문처리 배열을 두 개를 둔다.

vis배열은 0인 경우 아예 방문을 하지 않은 것이고, -1인 경우에는 방문을 했고, 더 이상 방문할 필요가 없다는 것이다.

1인 경우에는 현재 방문 중이라는 의미이다.

Done배열은 사이클을 이루는 성분인지 여부를 저장한다.

만약 학생 x를 한번 방문해서 vis[x]가 1인 상태라고 해보자. 즉 방문하고 있는 중이라는 것인데,

이 상태에서 x를 누군가가 또 방문한다는 것은? 학생 1을 포함하는 사이클이 존재한다는 의미이다.

따라서 x는 사이클이라는 것이 확실하기 때문에 done[x]를 true로 설정해준다.

그리고 cycle 검사를 마치면 (재귀를 탈출하면) 더 이상 방문할 필요가 없다는 의미이기 때문에 vis[x]를 -1로 만들어준다.

결과적으로 cycle검사의 탈출 조건은 이미 방문할 필요가 없는 곳이거나(vis가 -1인 경우)

이미 사이클을 이루고 있는 경우(Done이 1인 경우)인 것이다.

문제 링크는 다음과 같다.

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

수열에 오름차순이라는 조건이 존재하기 때문에 수열을 만들기 전에 입력받은 수들을 오름차순 정렬해준다.

또한 증가수열로 나타내야 하기 때문에 특정 자리의 숫자로는, 이 전 자리의 숫자보다 큰 숫자만 올 수 있다.

즉 길이 3인 수열을 만들어야 하는데, 첫 번째 숫자를 3으로 정해놨다고 하자.

3 _ _

이런 상태인데, 2번째 자리에 올 수 있는 숫자는 3보다 큰 숫자라는 뜻이다.

따라서 arr[k - 1] < num[i] 이 조건을 추가해서 구현해주면 된다.

물론 다음 재귀로 들어가기 전에 전역변수를 둬서 i를 저장해두거나, 재귀 함수의 인자로 몇 번째 index의 숫자를 사용했는지 관리해주는 방법도 있다.

func(1)은 이제 첫번째 자리의 숫자를 정해야 한다는 의미이다.

따라서 base condition은 이제 M+1번째 자리의 숫자를 정할 타이밍 일 것이다. 이때가 M번째 숫자까지 결정되었다는 의미이기 때문이다.

#include<iostream>
#include<algorithm>
using namespace std;
int N, M, num[10], arr[10];
bool isused[10];
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 (!isused[i] && num[i] > arr[k - 1]) {
			arr[k] = num[i];
			isused[i] = true;
			func(k + 1);
			isused[i] = false;
		}
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
		cin >> num[i];
	sort(num + 1, num + N + 1);
	
	func(1);
	return 0;
}